<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<!--[if IE]><meta http-equiv="X-UA-Compatible" content="IE=edge"><![endif]-->
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<meta name="generator" content="Asciidoctor 1.5.8">
<meta name="author" content="Peter Dimov">
<title>Simple C&#43;&#43;11 metaprogramming, part 2</title>
<link rel="stylesheet" href="https://fonts.googleapis.com/css?family=Open+Sans:300,300italic,400,400italic,600,600italic%7CNoto+Serif:400,400italic,700,700italic%7CDroid+Sans+Mono:400,700">
<style>
/* Asciidoctor default stylesheet | MIT License | http://asciidoctor.org */
/* Uncomment @import statement below to use as custom stylesheet */
/*@import "https://fonts.googleapis.com/css?family=Open+Sans:300,300italic,400,400italic,600,600italic%7CNoto+Serif:400,400italic,700,700italic%7CDroid+Sans+Mono:400,700";*/
article,aside,details,figcaption,figure,footer,header,hgroup,main,nav,section,summary{display:block}
audio,canvas,video{display:inline-block}
audio:not([controls]){display:none;height:0}
script{display:none!important}
html{font-family:sans-serif;-ms-text-size-adjust:100%;-webkit-text-size-adjust:100%}
a{background:transparent}
a:focus{outline:thin dotted}
a:active,a:hover{outline:0}
h1{font-size:2em;margin:.67em 0}
abbr[title]{border-bottom:1px dotted}
b,strong{font-weight:bold}
dfn{font-style:italic}
hr{-moz-box-sizing:content-box;box-sizing:content-box;height:0}
mark{background:#ff0;color:#000}
code,kbd,pre,samp{font-family:monospace;font-size:1em}
pre{white-space:pre-wrap}
q{quotes:"\201C" "\201D" "\2018" "\2019"}
small{font-size:80%}
sub,sup{font-size:75%;line-height:0;position:relative;vertical-align:baseline}
sup{top:-.5em}
sub{bottom:-.25em}
img{border:0}
svg:not(:root){overflow:hidden}
figure{margin:0}
fieldset{border:1px solid silver;margin:0 2px;padding:.35em .625em .75em}
legend{border:0;padding:0}
button,input,select,textarea{font-family:inherit;font-size:100%;margin:0}
button,input{line-height:normal}
button,select{text-transform:none}
button,html input[type="button"],input[type="reset"],input[type="submit"]{-webkit-appearance:button;cursor:pointer}
button[disabled],html input[disabled]{cursor:default}
input[type="checkbox"],input[type="radio"]{box-sizing:border-box;padding:0}
button::-moz-focus-inner,input::-moz-focus-inner{border:0;padding:0}
textarea{overflow:auto;vertical-align:top}
table{border-collapse:collapse;border-spacing:0}
*,*::before,*::after{-moz-box-sizing:border-box;-webkit-box-sizing:border-box;box-sizing:border-box}
html,body{font-size:100%}
body{background:#fff;color:rgba(0,0,0,.8);padding:0;margin:0;font-family:"Noto Serif","DejaVu Serif",serif;font-weight:400;font-style:normal;line-height:1;position:relative;cursor:auto;tab-size:4;-moz-osx-font-smoothing:grayscale;-webkit-font-smoothing:antialiased}
a:hover{cursor:pointer}
img,object,embed{max-width:100%;height:auto}
object,embed{height:100%}
img{-ms-interpolation-mode:bicubic}
.left{float:left!important}
.right{float:right!important}
.text-left{text-align:left!important}
.text-right{text-align:right!important}
.text-center{text-align:center!important}
.text-justify{text-align:justify!important}
.hide{display:none}
img,object,svg{display:inline-block;vertical-align:middle}
textarea{height:auto;min-height:50px}
select{width:100%}
.center{margin-left:auto;margin-right:auto}
.stretch{width:100%}
.subheader,.admonitionblock td.content>.title,.audioblock>.title,.exampleblock>.title,.imageblock>.title,.listingblock>.title,.literalblock>.title,.stemblock>.title,.openblock>.title,.paragraph>.title,.quoteblock>.title,table.tableblock>.title,.verseblock>.title,.videoblock>.title,.dlist>.title,.olist>.title,.ulist>.title,.qlist>.title,.hdlist>.title{line-height:1.45;color:#7a2518;font-weight:400;margin-top:0;margin-bottom:.25em}
div,dl,dt,dd,ul,ol,li,h1,h2,h3,#toctitle,.sidebarblock>.content>.title,h4,h5,h6,pre,form,p,blockquote,th,td{margin:0;padding:0;direction:ltr}
a{color:#2156a5;text-decoration:underline;line-height:inherit}
a:hover,a:focus{color:#1d4b8f}
a img{border:none}
p{font-family:inherit;font-weight:400;font-size:1em;line-height:1.6;margin-bottom:1.25em;text-rendering:optimizeLegibility}
p aside{font-size:.875em;line-height:1.35;font-style:italic}
h1,h2,h3,#toctitle,.sidebarblock>.content>.title,h4,h5,h6{font-family:"Open Sans","DejaVu Sans",sans-serif;font-weight:300;font-style:normal;color:#ba3925;text-rendering:optimizeLegibility;margin-top:1em;margin-bottom:.5em;line-height:1.0125em}
h1 small,h2 small,h3 small,#toctitle small,.sidebarblock>.content>.title small,h4 small,h5 small,h6 small{font-size:60%;color:#e99b8f;line-height:0}
h1{font-size:2.125em}
h2{font-size:1.6875em}
h3,#toctitle,.sidebarblock>.content>.title{font-size:1.375em}
h4,h5{font-size:1.125em}
h6{font-size:1em}
hr{border:solid #dddddf;border-width:1px 0 0;clear:both;margin:1.25em 0 1.1875em;height:0}
em,i{font-style:italic;line-height:inherit}
strong,b{font-weight:bold;line-height:inherit}
small{font-size:60%;line-height:inherit}
code{font-family:"Droid Sans Mono","DejaVu Sans Mono",monospace;font-weight:400;color:rgba(0,0,0,.9)}
ul,ol,dl{font-size:1em;line-height:1.6;margin-bottom:1.25em;list-style-position:outside;font-family:inherit}
ul,ol{margin-left:1.5em}
ul li ul,ul li ol{margin-left:1.25em;margin-bottom:0;font-size:1em}
ul.square li ul,ul.circle li ul,ul.disc li ul{list-style:inherit}
ul.square{list-style-type:square}
ul.circle{list-style-type:circle}
ul.disc{list-style-type:disc}
ol li ul,ol li ol{margin-left:1.25em;margin-bottom:0}
dl dt{margin-bottom:.3125em;font-weight:bold}
dl dd{margin-bottom:1.25em}
abbr,acronym{text-transform:uppercase;font-size:90%;color:rgba(0,0,0,.8);border-bottom:1px dotted #ddd;cursor:help}
abbr{text-transform:none}
blockquote{margin:0 0 1.25em;padding:.5625em 1.25em 0 1.1875em;border-left:1px solid #ddd}
blockquote cite{display:block;font-size:.9375em;color:rgba(0,0,0,.6)}
blockquote cite::before{content:"\2014 \0020"}
blockquote cite a,blockquote cite a:visited{color:rgba(0,0,0,.6)}
blockquote,blockquote p{line-height:1.6;color:rgba(0,0,0,.85)}
@media screen and (min-width:768px){h1,h2,h3,#toctitle,.sidebarblock>.content>.title,h4,h5,h6{line-height:1.2}
h1{font-size:2.75em}
h2{font-size:2.3125em}
h3,#toctitle,.sidebarblock>.content>.title{font-size:1.6875em}
h4{font-size:1.4375em}}
table{background:#fff;margin-bottom:1.25em;border:solid 1px #dedede}
table thead,table tfoot{background:#f7f8f7}
table thead tr th,table thead tr td,table tfoot tr th,table tfoot tr td{padding:.5em .625em .625em;font-size:inherit;color:rgba(0,0,0,.8);text-align:left}
table tr th,table tr td{padding:.5625em .625em;font-size:inherit;color:rgba(0,0,0,.8)}
table tr.even,table tr.alt,table tr:nth-of-type(even){background:#f8f8f7}
table thead tr th,table tfoot tr th,table tbody tr td,table tr td,table tfoot tr td{display:table-cell;line-height:1.6}
h1,h2,h3,#toctitle,.sidebarblock>.content>.title,h4,h5,h6{line-height:1.2;word-spacing:-.05em}
h1 strong,h2 strong,h3 strong,#toctitle strong,.sidebarblock>.content>.title strong,h4 strong,h5 strong,h6 strong{font-weight:400}
.clearfix::before,.clearfix::after,.float-group::before,.float-group::after{content:" ";display:table}
.clearfix::after,.float-group::after{clear:both}
*:not(pre)>code{font-size:.9375em;font-style:normal!important;letter-spacing:0;padding:.1em .5ex;word-spacing:-.15em;background-color:#f7f7f8;-webkit-border-radius:4px;border-radius:4px;line-height:1.45;text-rendering:optimizeSpeed;word-wrap:break-word}
*:not(pre)>code.nobreak{word-wrap:normal}
*:not(pre)>code.nowrap{white-space:nowrap}
pre,pre>code{line-height:1.45;color:rgba(0,0,0,.9);font-family:"Droid Sans Mono","DejaVu Sans Mono",monospace;font-weight:400;text-rendering:optimizeSpeed}
em em{font-style:normal}
strong strong{font-weight:400}
.keyseq{color:rgba(51,51,51,.8)}
kbd{font-family:"Droid Sans Mono","DejaVu Sans Mono",monospace;display:inline-block;color:rgba(0,0,0,.8);font-size:.65em;line-height:1.45;background-color:#f7f7f7;border:1px solid #ccc;-webkit-border-radius:3px;border-radius:3px;-webkit-box-shadow:0 1px 0 rgba(0,0,0,.2),0 0 0 .1em white inset;box-shadow:0 1px 0 rgba(0,0,0,.2),0 0 0 .1em #fff inset;margin:0 .15em;padding:.2em .5em;vertical-align:middle;position:relative;top:-.1em;white-space:nowrap}
.keyseq kbd:first-child{margin-left:0}
.keyseq kbd:last-child{margin-right:0}
.menuseq,.menuref{color:#000}
.menuseq b:not(.caret),.menuref{font-weight:inherit}
.menuseq{word-spacing:-.02em}
.menuseq b.caret{font-size:1.25em;line-height:.8}
.menuseq i.caret{font-weight:bold;text-align:center;width:.45em}
b.button::before,b.button::after{position:relative;top:-1px;font-weight:400}
b.button::before{content:"[";padding:0 3px 0 2px}
b.button::after{content:"]";padding:0 2px 0 3px}
p a>code:hover{color:rgba(0,0,0,.9)}
#header,#content,#footnotes,#footer{width:100%;margin-left:auto;margin-right:auto;margin-top:0;margin-bottom:0;max-width:62.5em;*zoom:1;position:relative;padding-left:.9375em;padding-right:.9375em}
#header::before,#header::after,#content::before,#content::after,#footnotes::before,#footnotes::after,#footer::before,#footer::after{content:" ";display:table}
#header::after,#content::after,#footnotes::after,#footer::after{clear:both}
#content{margin-top:1.25em}
#content::before{content:none}
#header>h1:first-child{color:rgba(0,0,0,.85);margin-top:2.25rem;margin-bottom:0}
#header>h1:first-child+#toc{margin-top:8px;border-top:1px solid #dddddf}
#header>h1:only-child,body.toc2 #header>h1:nth-last-child(2){border-bottom:1px solid #dddddf;padding-bottom:8px}
#header .details{border-bottom:1px solid #dddddf;line-height:1.45;padding-top:.25em;padding-bottom:.25em;padding-left:.25em;color:rgba(0,0,0,.6);display:-ms-flexbox;display:-webkit-flex;display:flex;-ms-flex-flow:row wrap;-webkit-flex-flow:row wrap;flex-flow:row wrap}
#header .details span:first-child{margin-left:-.125em}
#header .details span.email a{color:rgba(0,0,0,.85)}
#header .details br{display:none}
#header .details br+span::before{content:"\00a0\2013\00a0"}
#header .details br+span.author::before{content:"\00a0\22c5\00a0";color:rgba(0,0,0,.85)}
#header .details br+span#revremark::before{content:"\00a0|\00a0"}
#header #revnumber{text-transform:capitalize}
#header #revnumber::after{content:"\00a0"}
#content>h1:first-child:not([class]){color:rgba(0,0,0,.85);border-bottom:1px solid #dddddf;padding-bottom:8px;margin-top:0;padding-top:1rem;margin-bottom:1.25rem}
#toc{border-bottom:1px solid #e7e7e9;padding-bottom:.5em}
#toc>ul{margin-left:.125em}
#toc ul.sectlevel0>li>a{font-style:italic}
#toc ul.sectlevel0 ul.sectlevel1{margin:.5em 0}
#toc ul{font-family:"Open Sans","DejaVu Sans",sans-serif;list-style-type:none}
#toc li{line-height:1.3334;margin-top:.3334em}
#toc a{text-decoration:none}
#toc a:active{text-decoration:underline}
#toctitle{color:#7a2518;font-size:1.2em}
@media screen and (min-width:768px){#toctitle{font-size:1.375em}
body.toc2{padding-left:15em;padding-right:0}
#toc.toc2{margin-top:0!important;background-color:#f8f8f7;position:fixed;width:15em;left:0;top:0;border-right:1px solid #e7e7e9;border-top-width:0!important;border-bottom-width:0!important;z-index:1000;padding:1.25em 1em;height:100%;overflow:auto}
#toc.toc2 #toctitle{margin-top:0;margin-bottom:.8rem;font-size:1.2em}
#toc.toc2>ul{font-size:.9em;margin-bottom:0}
#toc.toc2 ul ul{margin-left:0;padding-left:1em}
#toc.toc2 ul.sectlevel0 ul.sectlevel1{padding-left:0;margin-top:.5em;margin-bottom:.5em}
body.toc2.toc-right{padding-left:0;padding-right:15em}
body.toc2.toc-right #toc.toc2{border-right-width:0;border-left:1px solid #e7e7e9;left:auto;right:0}}
@media screen and (min-width:1280px){body.toc2{padding-left:20em;padding-right:0}
#toc.toc2{width:20em}
#toc.toc2 #toctitle{font-size:1.375em}
#toc.toc2>ul{font-size:.95em}
#toc.toc2 ul ul{padding-left:1.25em}
body.toc2.toc-right{padding-left:0;padding-right:20em}}
#content #toc{border-style:solid;border-width:1px;border-color:#e0e0dc;margin-bottom:1.25em;padding:1.25em;background:#f8f8f7;-webkit-border-radius:4px;border-radius:4px}
#content #toc>:first-child{margin-top:0}
#content #toc>:last-child{margin-bottom:0}
#footer{max-width:100%;background-color:rgba(0,0,0,.8);padding:1.25em}
#footer-text{color:rgba(255,255,255,.8);line-height:1.44}
#content{margin-bottom:.625em}
.sect1{padding-bottom:.625em}
@media screen and (min-width:768px){#content{margin-bottom:1.25em}
.sect1{padding-bottom:1.25em}}
.sect1:last-child{padding-bottom:0}
.sect1+.sect1{border-top:1px solid #e7e7e9}
#content h1>a.anchor,h2>a.anchor,h3>a.anchor,#toctitle>a.anchor,.sidebarblock>.content>.title>a.anchor,h4>a.anchor,h5>a.anchor,h6>a.anchor{position:absolute;z-index:1001;width:1.5ex;margin-left:-1.5ex;display:block;text-decoration:none!important;visibility:hidden;text-align:center;font-weight:400}
#content h1>a.anchor::before,h2>a.anchor::before,h3>a.anchor::before,#toctitle>a.anchor::before,.sidebarblock>.content>.title>a.anchor::before,h4>a.anchor::before,h5>a.anchor::before,h6>a.anchor::before{content:"\00A7";font-size:.85em;display:block;padding-top:.1em}
#content h1:hover>a.anchor,#content h1>a.anchor:hover,h2:hover>a.anchor,h2>a.anchor:hover,h3:hover>a.anchor,#toctitle:hover>a.anchor,.sidebarblock>.content>.title:hover>a.anchor,h3>a.anchor:hover,#toctitle>a.anchor:hover,.sidebarblock>.content>.title>a.anchor:hover,h4:hover>a.anchor,h4>a.anchor:hover,h5:hover>a.anchor,h5>a.anchor:hover,h6:hover>a.anchor,h6>a.anchor:hover{visibility:visible}
#content h1>a.link,h2>a.link,h3>a.link,#toctitle>a.link,.sidebarblock>.content>.title>a.link,h4>a.link,h5>a.link,h6>a.link{color:#ba3925;text-decoration:none}
#content h1>a.link:hover,h2>a.link:hover,h3>a.link:hover,#toctitle>a.link:hover,.sidebarblock>.content>.title>a.link:hover,h4>a.link:hover,h5>a.link:hover,h6>a.link:hover{color:#a53221}
.audioblock,.imageblock,.literalblock,.listingblock,.stemblock,.videoblock{margin-bottom:1.25em}
.admonitionblock td.content>.title,.audioblock>.title,.exampleblock>.title,.imageblock>.title,.listingblock>.title,.literalblock>.title,.stemblock>.title,.openblock>.title,.paragraph>.title,.quoteblock>.title,table.tableblock>.title,.verseblock>.title,.videoblock>.title,.dlist>.title,.olist>.title,.ulist>.title,.qlist>.title,.hdlist>.title{text-rendering:optimizeLegibility;text-align:left;font-family:"Noto Serif","DejaVu Serif",serif;font-size:1rem;font-style:italic}
table.tableblock.fit-content>caption.title{white-space:nowrap;width:0}
.paragraph.lead>p,#preamble>.sectionbody>[class="paragraph"]:first-of-type p{font-size:1.21875em;line-height:1.6;color:rgba(0,0,0,.85)}
table.tableblock #preamble>.sectionbody>[class="paragraph"]:first-of-type p{font-size:inherit}
.admonitionblock>table{border-collapse:separate;border:0;background:none;width:100%}
.admonitionblock>table td.icon{text-align:center;width:80px}
.admonitionblock>table td.icon img{max-width:none}
.admonitionblock>table td.icon .title{font-weight:bold;font-family:"Open Sans","DejaVu Sans",sans-serif;text-transform:uppercase}
.admonitionblock>table td.content{padding-left:1.125em;padding-right:1.25em;border-left:1px solid #dddddf;color:rgba(0,0,0,.6)}
.admonitionblock>table td.content>:last-child>:last-child{margin-bottom:0}
.exampleblock>.content{border-style:solid;border-width:1px;border-color:#e6e6e6;margin-bottom:1.25em;padding:1.25em;background:#fff;-webkit-border-radius:4px;border-radius:4px}
.exampleblock>.content>:first-child{margin-top:0}
.exampleblock>.content>:last-child{margin-bottom:0}
.sidebarblock{border-style:solid;border-width:1px;border-color:#e0e0dc;margin-bottom:1.25em;padding:1.25em;background:#f8f8f7;-webkit-border-radius:4px;border-radius:4px}
.sidebarblock>:first-child{margin-top:0}
.sidebarblock>:last-child{margin-bottom:0}
.sidebarblock>.content>.title{color:#7a2518;margin-top:0;text-align:center}
.exampleblock>.content>:last-child>:last-child,.exampleblock>.content .olist>ol>li:last-child>:last-child,.exampleblock>.content .ulist>ul>li:last-child>:last-child,.exampleblock>.content .qlist>ol>li:last-child>:last-child,.sidebarblock>.content>:last-child>:last-child,.sidebarblock>.content .olist>ol>li:last-child>:last-child,.sidebarblock>.content .ulist>ul>li:last-child>:last-child,.sidebarblock>.content .qlist>ol>li:last-child>:last-child{margin-bottom:0}
.literalblock pre,.listingblock pre:not(.highlight),.listingblock pre[class="highlight"],.listingblock pre[class^="highlight "],.listingblock pre.CodeRay,.listingblock pre.prettyprint{background:#f7f7f8}
.sidebarblock .literalblock pre,.sidebarblock .listingblock pre:not(.highlight),.sidebarblock .listingblock pre[class="highlight"],.sidebarblock .listingblock pre[class^="highlight "],.sidebarblock .listingblock pre.CodeRay,.sidebarblock .listingblock pre.prettyprint{background:#f2f1f1}
.literalblock pre,.literalblock pre[class],.listingblock pre,.listingblock pre[class]{-webkit-border-radius:4px;border-radius:4px;word-wrap:break-word;overflow-x:auto;padding:1em;font-size:.8125em}
@media screen and (min-width:768px){.literalblock pre,.literalblock pre[class],.listingblock pre,.listingblock pre[class]{font-size:.90625em}}
@media screen and (min-width:1280px){.literalblock pre,.literalblock pre[class],.listingblock pre,.listingblock pre[class]{font-size:1em}}
.literalblock pre.nowrap,.literalblock pre.nowrap pre,.listingblock pre.nowrap,.listingblock pre.nowrap pre{white-space:pre;word-wrap:normal}
.literalblock.output pre{color:#f7f7f8;background-color:rgba(0,0,0,.9)}
.listingblock pre.highlightjs{padding:0}
.listingblock pre.highlightjs>code{padding:1em;-webkit-border-radius:4px;border-radius:4px}
.listingblock pre.prettyprint{border-width:0}
.listingblock>.content{position:relative}
.listingblock code[data-lang]::before{display:none;content:attr(data-lang);position:absolute;font-size:.75em;top:.425rem;right:.5rem;line-height:1;text-transform:uppercase;color:#999}
.listingblock:hover code[data-lang]::before{display:block}
.listingblock.terminal pre .command::before{content:attr(data-prompt);padding-right:.5em;color:#999}
.listingblock.terminal pre .command:not([data-prompt])::before{content:"$"}
table.pyhltable{border-collapse:separate;border:0;margin-bottom:0;background:none}
table.pyhltable td{vertical-align:top;padding-top:0;padding-bottom:0;line-height:1.45}
table.pyhltable td.code{padding-left:.75em;padding-right:0}
pre.pygments .lineno,table.pyhltable td:not(.code){color:#999;padding-left:0;padding-right:.5em;border-right:1px solid #dddddf}
pre.pygments .lineno{display:inline-block;margin-right:.25em}
table.pyhltable .linenodiv{background:none!important;padding-right:0!important}
.quoteblock{margin:0 1em 1.25em 1.5em;display:table}
.quoteblock>.title{margin-left:-1.5em;margin-bottom:.75em}
.quoteblock blockquote,.quoteblock p{color:rgba(0,0,0,.85);font-size:1.15rem;line-height:1.75;word-spacing:.1em;letter-spacing:0;font-style:italic;text-align:justify}
.quoteblock blockquote{margin:0;padding:0;border:0}
.quoteblock blockquote::before{content:"\201c";float:left;font-size:2.75em;font-weight:bold;line-height:.6em;margin-left:-.6em;color:#7a2518;text-shadow:0 1px 2px rgba(0,0,0,.1)}
.quoteblock blockquote>.paragraph:last-child p{margin-bottom:0}
.quoteblock .attribution{margin-top:.75em;margin-right:.5ex;text-align:right}
.verseblock{margin:0 1em 1.25em}
.verseblock pre{font-family:"Open Sans","DejaVu Sans",sans;font-size:1.15rem;color:rgba(0,0,0,.85);font-weight:300;text-rendering:optimizeLegibility}
.verseblock pre strong{font-weight:400}
.verseblock .attribution{margin-top:1.25rem;margin-left:.5ex}
.quoteblock .attribution,.verseblock .attribution{font-size:.9375em;line-height:1.45;font-style:italic}
.quoteblock .attribution br,.verseblock .attribution br{display:none}
.quoteblock .attribution cite,.verseblock .attribution cite{display:block;letter-spacing:-.025em;color:rgba(0,0,0,.6)}
.quoteblock.abstract blockquote::before,.quoteblock.excerpt blockquote::before,.quoteblock .quoteblock blockquote::before{display:none}
.quoteblock.abstract blockquote,.quoteblock.abstract p,.quoteblock.excerpt blockquote,.quoteblock.excerpt p,.quoteblock .quoteblock blockquote,.quoteblock .quoteblock p{line-height:1.6;word-spacing:0}
.quoteblock.abstract{margin:0 1em 1.25em;display:block}
.quoteblock.abstract>.title{margin:0 0 .375em;font-size:1.15em;text-align:center}
.quoteblock.excerpt,.quoteblock .quoteblock{margin:0 0 1.25em;padding:0 0 .25em 1em;border-left:.25em solid #dddddf}
.quoteblock.excerpt blockquote,.quoteblock.excerpt p,.quoteblock .quoteblock blockquote,.quoteblock .quoteblock p{color:inherit;font-size:1.0625rem}
.quoteblock.excerpt .attribution,.quoteblock .quoteblock .attribution{color:inherit;text-align:left;margin-right:0}
table.tableblock{max-width:100%;border-collapse:separate}
p.tableblock:last-child{margin-bottom:0}
td.tableblock>.content{margin-bottom:-1.25em}
table.tableblock,th.tableblock,td.tableblock{border:0 solid #dedede}
table.grid-all>thead>tr>.tableblock,table.grid-all>tbody>tr>.tableblock{border-width:0 1px 1px 0}
table.grid-all>tfoot>tr>.tableblock{border-width:1px 1px 0 0}
table.grid-cols>*>tr>.tableblock{border-width:0 1px 0 0}
table.grid-rows>thead>tr>.tableblock,table.grid-rows>tbody>tr>.tableblock{border-width:0 0 1px}
table.grid-rows>tfoot>tr>.tableblock{border-width:1px 0 0}
table.grid-all>*>tr>.tableblock:last-child,table.grid-cols>*>tr>.tableblock:last-child{border-right-width:0}
table.grid-all>tbody>tr:last-child>.tableblock,table.grid-all>thead:last-child>tr>.tableblock,table.grid-rows>tbody>tr:last-child>.tableblock,table.grid-rows>thead:last-child>tr>.tableblock{border-bottom-width:0}
table.frame-all{border-width:1px}
table.frame-sides{border-width:0 1px}
table.frame-topbot,table.frame-ends{border-width:1px 0}
table.stripes-all tr,table.stripes-odd tr:nth-of-type(odd){background:#f8f8f7}
table.stripes-none tr,table.stripes-odd tr:nth-of-type(even){background:none}
th.halign-left,td.halign-left{text-align:left}
th.halign-right,td.halign-right{text-align:right}
th.halign-center,td.halign-center{text-align:center}
th.valign-top,td.valign-top{vertical-align:top}
th.valign-bottom,td.valign-bottom{vertical-align:bottom}
th.valign-middle,td.valign-middle{vertical-align:middle}
table thead th,table tfoot th{font-weight:bold}
tbody tr th{display:table-cell;line-height:1.6;background:#f7f8f7}
tbody tr th,tbody tr th p,tfoot tr th,tfoot tr th p{color:rgba(0,0,0,.8);font-weight:bold}
p.tableblock>code:only-child{background:none;padding:0}
p.tableblock{font-size:1em}
td>div.verse{white-space:pre}
ol{margin-left:1.75em}
ul li ol{margin-left:1.5em}
dl dd{margin-left:1.125em}
dl dd:last-child,dl dd:last-child>:last-child{margin-bottom:0}
ol>li p,ul>li p,ul dd,ol dd,.olist .olist,.ulist .ulist,.ulist .olist,.olist .ulist{margin-bottom:.625em}
ul.checklist,ul.none,ol.none,ul.no-bullet,ol.no-bullet,ol.unnumbered,ul.unstyled,ol.unstyled{list-style-type:none}
ul.no-bullet,ol.no-bullet,ol.unnumbered{margin-left:.625em}
ul.unstyled,ol.unstyled{margin-left:0}
ul.checklist{margin-left:.625em}
ul.checklist li>p:first-child>.fa-square-o:first-child,ul.checklist li>p:first-child>.fa-check-square-o:first-child{width:1.25em;font-size:.8em;position:relative;bottom:.125em}
ul.checklist li>p:first-child>input[type="checkbox"]:first-child{margin-right:.25em}
ul.inline{display:-ms-flexbox;display:-webkit-box;display:flex;-ms-flex-flow:row wrap;-webkit-flex-flow:row wrap;flex-flow:row wrap;list-style:none;margin:0 0 .625em -1.25em}
ul.inline>li{margin-left:1.25em}
.unstyled dl dt{font-weight:400;font-style:normal}
ol.arabic{list-style-type:decimal}
ol.decimal{list-style-type:decimal-leading-zero}
ol.loweralpha{list-style-type:lower-alpha}
ol.upperalpha{list-style-type:upper-alpha}
ol.lowerroman{list-style-type:lower-roman}
ol.upperroman{list-style-type:upper-roman}
ol.lowergreek{list-style-type:lower-greek}
.hdlist>table,.colist>table{border:0;background:none}
.hdlist>table>tbody>tr,.colist>table>tbody>tr{background:none}
td.hdlist1,td.hdlist2{vertical-align:top;padding:0 .625em}
td.hdlist1{font-weight:bold;padding-bottom:1.25em}
.literalblock+.colist,.listingblock+.colist{margin-top:-.5em}
.colist td:not([class]):first-child{padding:.4em .75em 0;line-height:1;vertical-align:top}
.colist td:not([class]):first-child img{max-width:none}
.colist td:not([class]):last-child{padding:.25em 0}
.thumb,.th{line-height:0;display:inline-block;border:solid 4px #fff;-webkit-box-shadow:0 0 0 1px #ddd;box-shadow:0 0 0 1px #ddd}
.imageblock.left{margin:.25em .625em 1.25em 0}
.imageblock.right{margin:.25em 0 1.25em .625em}
.imageblock>.title{margin-bottom:0}
.imageblock.thumb,.imageblock.th{border-width:6px}
.imageblock.thumb>.title,.imageblock.th>.title{padding:0 .125em}
.image.left,.image.right{margin-top:.25em;margin-bottom:.25em;display:inline-block;line-height:0}
.image.left{margin-right:.625em}
.image.right{margin-left:.625em}
a.image{text-decoration:none;display:inline-block}
a.image object{pointer-events:none}
sup.footnote,sup.footnoteref{font-size:.875em;position:static;vertical-align:super}
sup.footnote a,sup.footnoteref a{text-decoration:none}
sup.footnote a:active,sup.footnoteref a:active{text-decoration:underline}
#footnotes{padding-top:.75em;padding-bottom:.75em;margin-bottom:.625em}
#footnotes hr{width:20%;min-width:6.25em;margin:-.25em 0 .75em;border-width:1px 0 0}
#footnotes .footnote{padding:0 .375em 0 .225em;line-height:1.3334;font-size:.875em;margin-left:1.2em;margin-bottom:.2em}
#footnotes .footnote a:first-of-type{font-weight:bold;text-decoration:none;margin-left:-1.05em}
#footnotes .footnote:last-of-type{margin-bottom:0}
#content #footnotes{margin-top:-.625em;margin-bottom:0;padding:.75em 0}
.gist .file-data>table{border:0;background:#fff;width:100%;margin-bottom:0}
.gist .file-data>table td.line-data{width:99%}
div.unbreakable{page-break-inside:avoid}
.big{font-size:larger}
.small{font-size:smaller}
.underline{text-decoration:underline}
.overline{text-decoration:overline}
.line-through{text-decoration:line-through}
.aqua{color:#00bfbf}
.aqua-background{background-color:#00fafa}
.black{color:#000}
.black-background{background-color:#000}
.blue{color:#0000bf}
.blue-background{background-color:#0000fa}
.fuchsia{color:#bf00bf}
.fuchsia-background{background-color:#fa00fa}
.gray{color:#606060}
.gray-background{background-color:#7d7d7d}
.green{color:#006000}
.green-background{background-color:#007d00}
.lime{color:#00bf00}
.lime-background{background-color:#00fa00}
.maroon{color:#600000}
.maroon-background{background-color:#7d0000}
.navy{color:#000060}
.navy-background{background-color:#00007d}
.olive{color:#606000}
.olive-background{background-color:#7d7d00}
.purple{color:#600060}
.purple-background{background-color:#7d007d}
.red{color:#bf0000}
.red-background{background-color:#fa0000}
.silver{color:#909090}
.silver-background{background-color:#bcbcbc}
.teal{color:#006060}
.teal-background{background-color:#007d7d}
.white{color:#bfbfbf}
.white-background{background-color:#fafafa}
.yellow{color:#bfbf00}
.yellow-background{background-color:#fafa00}
span.icon>.fa{cursor:default}
a span.icon>.fa{cursor:inherit}
.admonitionblock td.icon [class^="fa icon-"]{font-size:2.5em;text-shadow:1px 1px 2px rgba(0,0,0,.5);cursor:default}
.admonitionblock td.icon .icon-note::before{content:"\f05a";color:#19407c}
.admonitionblock td.icon .icon-tip::before{content:"\f0eb";text-shadow:1px 1px 2px rgba(155,155,0,.8);color:#111}
.admonitionblock td.icon .icon-warning::before{content:"\f071";color:#bf6900}
.admonitionblock td.icon .icon-caution::before{content:"\f06d";color:#bf3400}
.admonitionblock td.icon .icon-important::before{content:"\f06a";color:#bf0000}
.conum[data-value]{display:inline-block;color:#fff!important;background-color:rgba(0,0,0,.8);-webkit-border-radius:100px;border-radius:100px;text-align:center;font-size:.75em;width:1.67em;height:1.67em;line-height:1.67em;font-family:"Open Sans","DejaVu Sans",sans-serif;font-style:normal;font-weight:bold}
.conum[data-value] *{color:#fff!important}
.conum[data-value]+b{display:none}
.conum[data-value]::after{content:attr(data-value)}
pre .conum[data-value]{position:relative;top:-.125em}
b.conum *{color:inherit!important}
.conum:not([data-value]):empty{display:none}
dt,th.tableblock,td.content,div.footnote{text-rendering:optimizeLegibility}
h1,h2,p,td.content,span.alt{letter-spacing:-.01em}
p strong,td.content strong,div.footnote strong{letter-spacing:-.005em}
p,blockquote,dt,td.content,span.alt{font-size:1.0625rem}
p{margin-bottom:1.25rem}
.sidebarblock p,.sidebarblock dt,.sidebarblock td.content,p.tableblock{font-size:1em}
.exampleblock>.content{background-color:#fffef7;border-color:#e0e0dc;-webkit-box-shadow:0 1px 4px #e0e0dc;box-shadow:0 1px 4px #e0e0dc}
.print-only{display:none!important}
@page{margin:1.25cm .75cm}
@media print{*{-webkit-box-shadow:none!important;box-shadow:none!important;text-shadow:none!important}
html{font-size:80%}
a{color:inherit!important;text-decoration:underline!important}
a.bare,a[href^="#"],a[href^="mailto:"]{text-decoration:none!important}
a[href^="http:"]:not(.bare)::after,a[href^="https:"]:not(.bare)::after{content:"(" attr(href) ")";display:inline-block;font-size:.875em;padding-left:.25em}
abbr[title]::after{content:" (" attr(title) ")"}
pre,blockquote,tr,img,object,svg{page-break-inside:avoid}
thead{display:table-header-group}
svg{max-width:100%}
p,blockquote,dt,td.content{font-size:1em;orphans:3;widows:3}
h2,h3,#toctitle,.sidebarblock>.content>.title{page-break-after:avoid}
#toc,.sidebarblock,.exampleblock>.content{background:none!important}
#toc{border-bottom:1px solid #dddddf!important;padding-bottom:0!important}
body.book #header{text-align:center}
body.book #header>h1:first-child{border:0!important;margin:2.5em 0 1em}
body.book #header .details{border:0!important;display:block;padding:0!important}
body.book #header .details span:first-child{margin-left:0!important}
body.book #header .details br{display:block}
body.book #header .details br+span::before{content:none!important}
body.book #toc{border:0!important;text-align:left!important;padding:0!important;margin:0!important}
body.book #toc,body.book #preamble,body.book h1.sect0,body.book .sect1>h2{page-break-before:always}
.listingblock code[data-lang]::before{display:block}
#footer{padding:0 .9375em}
.hide-on-print{display:none!important}
.print-only{display:block!important}
.hide-for-print{display:none!important}
.show-for-print{display:inherit!important}}
@media print,amzn-kf8{#header>h1:first-child{margin-top:1.25rem}
.sect1{padding:0!important}
.sect1+.sect1{border:0}
#footer{background:none}
#footer-text{color:rgba(0,0,0,.6);font-size:.9em}}
@media amzn-kf8{#header,#content,#footnotes,#footer{padding:0}}
</style>
</head>
<body class="article toc2 toc-left">
<div id="header">
<h1>Simple C&#43;&#43;11 metaprogramming, part 2</h1>
<div class="details">
<span id="author" class="author">Peter Dimov</span><br>
<span id="revdate">2015-06-20</span>
</div>
<div id="toc" class="toc2">
<div id="toctitle">Table of Contents</div>
<ul class="sectlevel1">
<li><a href="#vectors_sets_and_maps">Vectors, sets, and maps</a></li>
<li><a href="#mp_contains">mp_contains</a></li>
<li><a href="#mp_map_find">mp_map_find</a></li>
<li><a href="#mp_at">mp_at</a></li>
<li><a href="#mp_drop">mp_drop</a></li>
<li><a href="#mp_find_index">mp_find_index</a></li>
<li><a href="#conclusion">Conclusion</a></li>
</ul>
</div>
</div>
<div id="content">
<div id="preamble">
<div class="sectionbody">
<div class="paragraph lead">
<p><em>Efficient algorithms for membership testing, random access, and retrieval by
key</em></p>
</div>
<div class="admonitionblock note">
<table>
<tr>
<td class="icon">
<div class="title">Note</div>
</td>
<td class="content">
Being late to the metaprogramming party, I make no claim of having
invented the techniques in this article. A quick look at the implementations
of, for example, Louis Dionne&#8217;s <a href="https://github.com/ldionne/mpl11">mpl11</a> and
Eric Niebler&#8217;s <a href="https://github.com/ericniebler/meta">meta</a>, shows that most of
these tricks are already known. Dave Abrahams
<a href="https://github.com/dabrahams/mpl11">has experimented</a> along these lines in 2012.
The original inventor of the multiple inheritance trick and the <code>void*</code>
arguments trick is probably Richard Smith, who has posted
<a href="https://llvm.org/bugs/attachment.cgi?id=8825">two</a>
<a href="https://llvm.org/bugs/attachment.cgi?id=8838">examples</a> in response to
<a href="https://llvm.org/bugs/show_bug.cgi?id=13263">a Clang bug report</a>.
</td>
</tr>
</table>
</div>
</div>
</div>
<div class="sect1">
<h2 id="vectors_sets_and_maps">Vectors, sets, and maps</h2>
<div class="sectionbody">
<div class="paragraph">
<p><a href="simple_cxx11_metaprogramming.html">Last time</a>, I outlined a style of
metaprogramming that operated on type lists&#8201;&#8212;&#8201;variadic class templates:</p>
</div>
<div class="listingblock">
<div class="content">
<pre class="highlight"><code>template&lt;class... T&gt; struct mp_list {};</code></pre>
</div>
</div>
<div class="paragraph">
<p>Classic Lisp uses lists as its only data structure, but operating on a list is
usually linear in the number of its elements.</p>
</div>
<div class="paragraph">
<p>In addition to <code>list</code>, the STL has <code>vector</code>, <code>set</code>, and <code>map</code>. <code>vector</code>
supports random access by index; <code>set</code> has efficient test for membership; <code>map</code>
associates keys with values and has efficient lookup based on key.</p>
</div>
<div class="paragraph">
<p>Instead of introducing separate data structure such as <code>mp_vector</code>, <code>mp_set</code>,
<code>mp_map</code>, we&#8217;ll keep our data in a list form, and attempt to provide efficient
algorithms for random access, membership testing, and lookup.</p>
</div>
</div>
</div>
<div class="sect1">
<h2 id="mp_contains">mp_contains</h2>
<div class="sectionbody">
<div class="paragraph">
<p>Let&#8217;s starts with sets. A set is just a list with unique elements. To obtain a
set from an arbitrary list, we&#8217;ll need an algorithm that removes the
duplicates. Let&#8217;s call it <code>mp_unique&lt;L&gt;</code>:</p>
</div>
<div class="listingblock">
<div class="content">
<pre class="highlight"><code>// mp_if

template&lt;bool C, class T, class E&gt; struct mp_if_c_impl;

template&lt;class T, class E&gt; struct mp_if_c_impl&lt;true, T, E&gt;
{
    using type = T;
};

template&lt;class T, class E&gt; struct mp_if_c_impl&lt;false, T, E&gt;
{
    using type = E;
};

template&lt;bool C, class T, class E&gt;
    using mp_if_c = typename mp_if_c_impl&lt;C, T, E&gt;::type;

template&lt;class C, class T, class E&gt;
    using mp_if = typename mp_if_c_impl&lt;C::value != 0, T, E&gt;::type;

// mp_unique

template&lt;class L&gt; struct mp_unique_impl;

template&lt;class L&gt; using mp_unique = typename mp_unique_impl&lt;L&gt;::type;

template&lt;template&lt;class...&gt; class L&gt; struct mp_unique_impl&lt;L&lt;&gt;&gt;
{
    using type = L&lt;&gt;;
};

template&lt;template&lt;class...&gt; class L, class T1, class... T&gt;
    struct mp_unique_impl&lt;L&lt;T1, T...&gt;&gt;
{
    using _rest = mp_unique&lt;L&lt;T...&gt;&gt;;
    using type = mp_if&lt;<strong>mp_contains</strong>&lt;_rest, T1&gt;, _rest, mp_push_front&lt;_rest, T1&gt;&gt;;
};</code></pre>
</div>
</div>
<div class="paragraph">
<p>For membership testing, we&#8217;ve introduced an algorithm <code>mp_contains&lt;L, V&gt;</code> that
returns <code>true</code> when <code>L</code> contains <code>V</code>. The straightforward recursive
implementation of <code>mp_contains</code> is:</p>
</div>
<div class="listingblock">
<div class="content">
<pre class="highlight"><code>template&lt;class L, class V&gt; struct mp_contains_impl;

template&lt;class L, class V&gt; using mp_contains = typename mp_contains_impl&lt;L, V&gt;::type;

template&lt;template&lt;class...&gt; class L, class V&gt; struct mp_contains_impl&lt;L&lt;&gt;, V&gt;
{
    using type = std::false_type;
};

template&lt;template&lt;class...&gt; class L, class... T, class V&gt;
    struct mp_contains_impl&lt;L&lt;V, T...&gt;, V&gt;
{
    using type = std::true_type;
};

template&lt;template&lt;class...&gt; class L, class T1, class... T, class V&gt;
    struct mp_contains_impl&lt;L&lt;T1, T...&gt;, V&gt;: mp_contains_impl&lt;L&lt;T...&gt;, V&gt;
{
};</code></pre>
</div>
</div>
<div class="paragraph">
<p>Note that <code>mp_unique&lt;L&gt;</code> makes <code>N</code> calls to <code>mp_contains</code>, where <code>N</code> is the
length of the list <code>L</code>. This means that <code>mp_contains</code> needs to be as fast as
possible, which the above implementation, well, isn&#8217;t.</p>
</div>
<div class="paragraph">
<p>Here are the compile times in seconds for invoking <code>mp_unique</code> on a list with
<code>N</code> (distinct) elements:</p>
</div>
<table class="tableblock frame-all grid-all stretch">
<colgroup>
<col style="width: 11.1111%;">
<col style="width: 11.1111%;">
<col style="width: 11.1111%;">
<col style="width: 11.1111%;">
<col style="width: 11.1111%;">
<col style="width: 11.1111%;">
<col style="width: 11.1111%;">
<col style="width: 11.1111%;">
<col style="width: 11.1112%;">
</colgroup>
<thead>
<tr>
<th class="tableblock halign-left valign-top"></th>
<th class="tableblock halign-left valign-top">N=100</th>
<th class="tableblock halign-left valign-top">N=200</th>
<th class="tableblock halign-left valign-top">N=300</th>
<th class="tableblock halign-left valign-top">N=400</th>
<th class="tableblock halign-left valign-top">N=500</th>
<th class="tableblock halign-left valign-top">N=600</th>
<th class="tableblock halign-left valign-top">N=700</th>
<th class="tableblock halign-left valign-top">N=800</th>
</tr>
</thead>
<tbody>
<tr>
<td class="tableblock halign-left valign-top"><p class="tableblock">VC++ 2013, recursive</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">2.1</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">DNF</p></td>
<td class="tableblock halign-left valign-top"></td>
<td class="tableblock halign-left valign-top"></td>
<td class="tableblock halign-left valign-top"></td>
<td class="tableblock halign-left valign-top"></td>
<td class="tableblock halign-left valign-top"></td>
<td class="tableblock halign-left valign-top"></td>
</tr>
<tr>
<td class="tableblock halign-left valign-top"><p class="tableblock">clang++ 3.5.1, recursive</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">0.9</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">4.5</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">13.2</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">30.2</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">DNF</p></td>
<td class="tableblock halign-left valign-top"></td>
<td class="tableblock halign-left valign-top"></td>
<td class="tableblock halign-left valign-top"></td>
</tr>
<tr>
<td class="tableblock halign-left valign-top"><p class="tableblock">g++ 4.9.2, recursive</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">0.7</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">3.6</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">10.4</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">23.2</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">DNF</p></td>
<td class="tableblock halign-left valign-top"></td>
<td class="tableblock halign-left valign-top"></td>
<td class="tableblock halign-left valign-top"></td>
</tr>
</tbody>
</table>
<div class="paragraph">
<p>(Tests done under Windows/Cygwin. All compilers are 32 bit. No optimizations.
DNF stands for "did not finish", which usually means that the compiler ran out
of heap space or crashed.)</p>
</div>
<div class="paragraph">
<p>We clearly need a better alternative.</p>
</div>
<div class="paragraph">
<p>I ended the previous article with an implementation of <code>mp_contains</code> that
relied on <code>mp_count</code>, which in turn relied on <code>mp_plus</code>. Let&#8217;s see how it
fares:</p>
</div>
<table class="tableblock frame-all grid-all stretch">
<colgroup>
<col style="width: 11.1111%;">
<col style="width: 11.1111%;">
<col style="width: 11.1111%;">
<col style="width: 11.1111%;">
<col style="width: 11.1111%;">
<col style="width: 11.1111%;">
<col style="width: 11.1111%;">
<col style="width: 11.1111%;">
<col style="width: 11.1112%;">
</colgroup>
<thead>
<tr>
<th class="tableblock halign-left valign-top"></th>
<th class="tableblock halign-left valign-top">N=100</th>
<th class="tableblock halign-left valign-top">N=200</th>
<th class="tableblock halign-left valign-top">N=300</th>
<th class="tableblock halign-left valign-top">N=400</th>
<th class="tableblock halign-left valign-top">N=500</th>
<th class="tableblock halign-left valign-top">N=600</th>
<th class="tableblock halign-left valign-top">N=700</th>
<th class="tableblock halign-left valign-top">N=800</th>
</tr>
</thead>
<tbody>
<tr>
<td class="tableblock halign-left valign-top"><p class="tableblock">VC++ 2013, mp_count/mp_plus</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">1.1</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">9.8</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">50.5</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">DNF</p></td>
<td class="tableblock halign-left valign-top"></td>
<td class="tableblock halign-left valign-top"></td>
<td class="tableblock halign-left valign-top"></td>
<td class="tableblock halign-left valign-top"></td>
</tr>
<tr>
<td class="tableblock halign-left valign-top"><p class="tableblock">clang++ 3.5.1, mp_count/mp_plus</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">0.5</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">1.4</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">3.1</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">6.1</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">DNF</p></td>
<td class="tableblock halign-left valign-top"></td>
<td class="tableblock halign-left valign-top"></td>
<td class="tableblock halign-left valign-top"></td>
</tr>
<tr>
<td class="tableblock halign-left valign-top"><p class="tableblock">g++ 4.9.2, mp_count/mp_plus</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">0.5</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">1.3</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">2.9</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">5.8</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">9.7</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">15.6</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">22.4</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">32.3</p></td>
</tr>
</tbody>
</table>
<div class="paragraph">
<p>Not <em>that</em> bad, at least if your compiler happens to be <code>g++</code>. Still, there
ought to be room for improvement here.</p>
</div>
<div class="paragraph">
<p>To do better, we have to somehow leverage the language features, such as pack
expansion, to do more of the work for us. For inspiration, let&#8217;s turn to
section 14.5.3 paragraph 4 of the C&#43;&#43;11 standard, which explains that pack
expansions can occur in the following contexts:</p>
</div>
<div class="ulist">
<ul>
<li>
<p><strong>In a function parameter pack (8.3.5); the pattern is the
<em>parameter-declaration</em> without the ellipsis.</strong></p>
</li>
<li>
<p>In a template parameter pack that is a pack expansion (14.1):</p>
</li>
<li>
<p><strong>In an <em>initializer-list</em> (8.5); the pattern is an
<em>initializer-clause</em>.</strong></p>
</li>
<li>
<p><strong>In a <em>base-specifier-list</em> (Clause 10); the pattern is a
<em>base-specifier</em>.</strong></p>
</li>
<li>
<p>In a <em>mem-initializer-list</em> (12.6.2); the pattern is a
<em>mem-initializer</em>.</p>
</li>
<li>
<p>In a <em>template-argument-list</em> (14.3); the pattern is a
<em>template-argument</em>.</p>
</li>
<li>
<p>In a <em>dynamic-exception-specification</em> (15.4); the pattern is a
<em>type-id</em>.</p>
</li>
<li>
<p>In an <em>attribute-list</em> (7.6.1); the pattern is an <em>attribute</em>.</p>
</li>
<li>
<p>In an <em>alignment-specifier</em> (7.6.2); the pattern is the
<em>alignment-specifier</em> without the ellipsis.</p>
</li>
<li>
<p>In a <em>capture-list</em> (5.1.2); the pattern is a <em>capture</em>.</p>
</li>
<li>
<p>In a <code>sizeof...</code> expression (5.3.3); the pattern is an <em>identifier</em>.</p>
</li>
</ul>
</div>
<div class="paragraph">
<p>The <strong>emphasis</strong> is mine and indicates possible leads.</p>
</div>
<div class="paragraph">
<p>Our first option is to expand the parameter pack into arguments for a function
call. Since we&#8217;re interested in operations that occur at compile time, calling
a function may not appear useful; but C&#43;&#43;11 functions can be <code>constexpr</code>, and
<code>constexpr</code> function "calls" do occur at compile time.</p>
</div>
<div class="paragraph">
<p>Recall our <code>mp_count</code>:</p>
</div>
<div class="listingblock">
<div class="content">
<pre class="highlight"><code>template&lt;class L, class V&gt; struct mp_count_impl;

template&lt;template&lt;class...&gt; class L, class... T, class V&gt;
    struct mp_count_impl&lt;L&lt;T...&gt;, V&gt;
{
    using type = mp_plus&lt;std::is_same&lt;T, V&gt;...&gt;;
};

template&lt;class L, class V&gt; using mp_count = typename mp_count_impl&lt;L, V&gt;::type;</code></pre>
</div>
</div>
<div class="paragraph">
<p>Instead of using the template alias <code>mp_plus</code> to sum the <code>is_same</code> expressions,
we can use a <code>constexpr</code> function:</p>
</div>
<div class="listingblock">
<div class="content">
<pre class="highlight"><code>constexpr std::size_t cx_plus()
{
    return 0;
}

template&lt;class T1, class... T&gt; constexpr std::size_t cx_plus(T1 t1, T... t)
{
    return t1 + cx_plus(t...);
}

// mp_size_t

template&lt;std::size_t N&gt; using mp_size_t = std::integral_constant&lt;std::size_t, N&gt;;

// mp_count

template&lt;class L, class V&gt; struct mp_count_impl;

template&lt;template&lt;class...&gt; class L, class... T, class V&gt;
    struct mp_count_impl&lt;L&lt;T...&gt;, V&gt;
{
    using type = mp_size_t&lt;cx_plus(std::is_same&lt;T, V&gt;::value...)&gt;;
};

template&lt;class L, class V&gt; using mp_count = typename mp_count_impl&lt;L, V&gt;::type;</code></pre>
</div>
</div>
<div class="paragraph">
<p>with the following results:</p>
</div>
<table class="tableblock frame-all grid-all stretch">
<colgroup>
<col style="width: 11.1111%;">
<col style="width: 11.1111%;">
<col style="width: 11.1111%;">
<col style="width: 11.1111%;">
<col style="width: 11.1111%;">
<col style="width: 11.1111%;">
<col style="width: 11.1111%;">
<col style="width: 11.1111%;">
<col style="width: 11.1112%;">
</colgroup>
<thead>
<tr>
<th class="tableblock halign-left valign-top"></th>
<th class="tableblock halign-left valign-top">N=100</th>
<th class="tableblock halign-left valign-top">N=200</th>
<th class="tableblock halign-left valign-top">N=300</th>
<th class="tableblock halign-left valign-top">N=400</th>
<th class="tableblock halign-left valign-top">N=500</th>
<th class="tableblock halign-left valign-top">N=600</th>
<th class="tableblock halign-left valign-top">N=700</th>
<th class="tableblock halign-left valign-top">N=800</th>
</tr>
</thead>
<tbody>
<tr>
<td class="tableblock halign-left valign-top"><p class="tableblock">clang++ 3.5.1, mp_count/cx_plus</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">0.4</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">1.1</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">2.5</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">5.0</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">DNF</p></td>
<td class="tableblock halign-left valign-top"></td>
<td class="tableblock halign-left valign-top"></td>
<td class="tableblock halign-left valign-top"></td>
</tr>
<tr>
<td class="tableblock halign-left valign-top"><p class="tableblock">g++ 4.9.2, mp_count/cx_plus</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">0.4</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">0.9</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">1.7</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">2.9</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">4.7</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">6.7</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">9.2</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">11.8</p></td>
</tr>
</tbody>
</table>
<div class="paragraph">
<p>We&#8217;ve improved the times, but lost VC++ 2013 due to its not implementing
<code>constexpr</code>.</p>
</div>
<div class="paragraph">
<p>Let&#8217;s try pack expansion into an <em>initializer-list</em>. Instead of passing the
<code>is_same</code> expressions to a function, we can build a constant array out of them,
then sum the array with a <code>constexpr</code> function:</p>
</div>
<div class="listingblock">
<div class="content">
<pre class="highlight"><code>constexpr std::size_t cx_plus2(bool const * first, bool const * last)
{
    return first == last? 0: *first + cx_plus2(first + 1, last);
}

// mp_count

template&lt;class L, class V&gt; struct mp_count_impl;

template&lt;template&lt;class...&gt; class L, class... T, class V&gt;
    struct mp_count_impl&lt;L&lt;T...&gt;, V&gt;
{
    static constexpr bool _v[] = { std::is_same&lt;T, V&gt;::value... };
    using type = mp_size_t&lt;cx_plus2(_v, _v + sizeof...(T))&gt;;
};

template&lt;class L, class V&gt; using mp_count = typename mp_count_impl&lt;L, V&gt;::type;</code></pre>
</div>
</div>
<div class="paragraph">
<p>This is a neat trick, but is it fast?</p>
</div>
<table class="tableblock frame-all grid-all stretch">
<colgroup>
<col style="width: 11.1111%;">
<col style="width: 11.1111%;">
<col style="width: 11.1111%;">
<col style="width: 11.1111%;">
<col style="width: 11.1111%;">
<col style="width: 11.1111%;">
<col style="width: 11.1111%;">
<col style="width: 11.1111%;">
<col style="width: 11.1112%;">
</colgroup>
<thead>
<tr>
<th class="tableblock halign-left valign-top"></th>
<th class="tableblock halign-left valign-top">N=100</th>
<th class="tableblock halign-left valign-top">N=200</th>
<th class="tableblock halign-left valign-top">N=300</th>
<th class="tableblock halign-left valign-top">N=400</th>
<th class="tableblock halign-left valign-top">N=500</th>
<th class="tableblock halign-left valign-top">N=600</th>
<th class="tableblock halign-left valign-top">N=700</th>
<th class="tableblock halign-left valign-top">N=800</th>
</tr>
</thead>
<tbody>
<tr>
<td class="tableblock halign-left valign-top"><p class="tableblock">clang++ 3.5.1, mp_count/cx_plus2</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">0.4</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">0.9</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">1.8</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">DNF</p></td>
<td class="tableblock halign-left valign-top"></td>
<td class="tableblock halign-left valign-top"></td>
<td class="tableblock halign-left valign-top"></td>
<td class="tableblock halign-left valign-top"></td>
</tr>
<tr>
<td class="tableblock halign-left valign-top"><p class="tableblock">g++ 4.9.2, mp_count/cx_plus2</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">0.4</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">0.9</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">1.9</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">3.4</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">5.4</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">7.8</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">11.0</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">14.7</p></td>
</tr>
</tbody>
</table>
<div class="paragraph">
<p>That&#8217;s a bit disappointing. Let&#8217;s see what can we do with expanding a parameter
pack into a base-specifier-list. We would be able to define a class that
derives from every element of the pack:</p>
</div>
<div class="listingblock">
<div class="content">
<pre class="highlight"><code>struct U: T... {};</code></pre>
</div>
</div>
<div class="paragraph">
<p>We can then use <code>std::is_base_of&lt;V, U&gt;</code> to test whether a type <code>V</code> is a base of
<code>U</code>, that is, whether it&#8217;s one of the elements of the parameter pack. Which is
exactly what we need.</p>
</div>
<div class="paragraph">
<p>Arbitrary types such as <code>void</code>, <code>int</code>, or <code>void(int)</code> can&#8217;t be used as base
classes, but we&#8217;ll wrap the types in an empty class template, which we&#8217;ll call
<code>mp_identity</code>.</p>
</div>
<div class="listingblock">
<div class="content">
<pre class="highlight"><code>template&lt;class T&gt; struct mp_identity
{
    using type = T;
};

template&lt;class L, class V&gt; struct mp_contains_impl;

template&lt;class L, class V&gt; using mp_contains = typename mp_contains_impl&lt;L, V&gt;::type;

template&lt;template&lt;class...&gt; class L, class... T, class V&gt;
    struct mp_contains_impl&lt;L&lt;T...&gt;, V&gt;
{
    struct U: mp_identity&lt;T&gt;... {};
    using type = std::is_base_of&lt;mp_identity&lt;V&gt;, U&gt;;
};</code></pre>
</div>
</div>
<div class="paragraph">
<p>Performance?</p>
</div>
<table class="tableblock frame-all grid-all stretch">
<colgroup>
<col style="width: 11.1111%;">
<col style="width: 11.1111%;">
<col style="width: 11.1111%;">
<col style="width: 11.1111%;">
<col style="width: 11.1111%;">
<col style="width: 11.1111%;">
<col style="width: 11.1111%;">
<col style="width: 11.1111%;">
<col style="width: 11.1112%;">
</colgroup>
<thead>
<tr>
<th class="tableblock halign-left valign-top"></th>
<th class="tableblock halign-left valign-top">N=100</th>
<th class="tableblock halign-left valign-top">N=200</th>
<th class="tableblock halign-left valign-top">N=300</th>
<th class="tableblock halign-left valign-top">N=400</th>
<th class="tableblock halign-left valign-top">N=500</th>
<th class="tableblock halign-left valign-top">N=600</th>
<th class="tableblock halign-left valign-top">N=700</th>
<th class="tableblock halign-left valign-top">N=800</th>
</tr>
</thead>
<tbody>
<tr>
<td class="tableblock halign-left valign-top"><p class="tableblock">VC++ 2013, is_base_of</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">0.3</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">0.6</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">1.3</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">2.5</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">DNF</p></td>
<td class="tableblock halign-left valign-top"></td>
<td class="tableblock halign-left valign-top"></td>
<td class="tableblock halign-left valign-top"></td>
</tr>
<tr>
<td class="tableblock halign-left valign-top"><p class="tableblock">clang++ 3.5.1, is_base_of</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">0.3</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">0.4</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">0.6</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">0.8</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">DNF</p></td>
<td class="tableblock halign-left valign-top"></td>
<td class="tableblock halign-left valign-top"></td>
<td class="tableblock halign-left valign-top"></td>
</tr>
<tr>
<td class="tableblock halign-left valign-top"><p class="tableblock">g++ 4.9.2, is_base_of</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">0.3</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">0.4</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">0.6</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">0.9</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">1.3</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">1.7</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">2.3</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">3.0</p></td>
</tr>
</tbody>
</table>
<div class="paragraph">
<p>This implementation is a clear winner.</p>
</div>
<div class="paragraph">
<p>In fairness, we ought to note that the first four implementations of
<code>mp_contains</code> do not rely on the list elements being unique. This makes
<code>mp_contains</code> an algorithm that supports arbitrary lists, not just sets.</p>
</div>
<div class="paragraph">
<p>The <code>is_base_of</code> implementation, however, does not support lists that contain
duplicates, because it&#8217;s not possible to inherit directly from the same type
twice. So it does not implement the general <code>mp_contains</code>, but something that
should probably be named <code>mp_set_contains</code>.</p>
</div>
<div class="paragraph">
<p>We can avoid the "no duplicates" requirement by modifying the implementation to
inherit from <code>mp_identity&lt;T&gt;</code> indirectly, via an intermediate base class:</p>
</div>
<div class="listingblock">
<div class="content">
<pre class="highlight"><code>// indirect_inherit

template&lt;std::size_t I, class T&gt; struct inherit_second: T {};

template&lt;class L, class S&gt; struct indirect_inherit_impl;

template&lt;template&lt;class...&gt; class L, class... T, std::size_t... J&gt;
    struct indirect_inherit_impl&lt;L&lt;T...&gt;, <a href="http://en.cppreference.com/w/cpp/utility/integer_sequence">integer_sequence</a>&lt;std::size_t, J...&gt;&gt;:
        inherit_second&lt;J, mp_identity&lt;T&gt;&gt;... {};

template&lt;class L&gt; using indirect_inherit =
    indirect_inherit_impl&lt;L, <a href="http://en.cppreference.com/w/cpp/utility/integer_sequence">make_index_sequence</a>&lt;mp_size&lt;L&gt;::value&gt;&gt;;

// mp_contains

template&lt;class L, class V&gt; struct mp_contains_impl
{
    using U = indirect_inherit&lt;L&gt;;
    using type = std::is_base_of&lt;mp_identity&lt;V&gt;, U&gt;;
};

template&lt;class L, class V&gt; using mp_contains = typename mp_contains_impl&lt;L, V&gt;::type;</code></pre>
</div>
</div>
<div class="paragraph">
<p>This, however, pretty much nullifies the spectacular performance gains we&#8217;ve
observed with the original <code>is_base_of</code>-based implementation:</p>
</div>
<table class="tableblock frame-all grid-all stretch">
<colgroup>
<col style="width: 11.1111%;">
<col style="width: 11.1111%;">
<col style="width: 11.1111%;">
<col style="width: 11.1111%;">
<col style="width: 11.1111%;">
<col style="width: 11.1111%;">
<col style="width: 11.1111%;">
<col style="width: 11.1111%;">
<col style="width: 11.1112%;">
</colgroup>
<thead>
<tr>
<th class="tableblock halign-left valign-top"></th>
<th class="tableblock halign-left valign-top">N=100</th>
<th class="tableblock halign-left valign-top">N=200</th>
<th class="tableblock halign-left valign-top">N=300</th>
<th class="tableblock halign-left valign-top">N=400</th>
<th class="tableblock halign-left valign-top">N=500</th>
<th class="tableblock halign-left valign-top">N=600</th>
<th class="tableblock halign-left valign-top">N=700</th>
<th class="tableblock halign-left valign-top">N=800</th>
</tr>
</thead>
<tbody>
<tr>
<td class="tableblock halign-left valign-top"><p class="tableblock">VC++ 2013, recursive</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">2.1</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">DNF</p></td>
<td class="tableblock halign-left valign-top"></td>
<td class="tableblock halign-left valign-top"></td>
<td class="tableblock halign-left valign-top"></td>
<td class="tableblock halign-left valign-top"></td>
<td class="tableblock halign-left valign-top"></td>
<td class="tableblock halign-left valign-top"></td>
</tr>
<tr>
<td class="tableblock halign-left valign-top"><p class="tableblock">VC++ 2013, mp_count/mp_plus</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">1.1</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">9.8</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">50.5</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">DNF</p></td>
<td class="tableblock halign-left valign-top"></td>
<td class="tableblock halign-left valign-top"></td>
<td class="tableblock halign-left valign-top"></td>
<td class="tableblock halign-left valign-top"></td>
</tr>
<tr>
<td class="tableblock halign-left valign-top"><p class="tableblock">VC++ 2013, is_base_of</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">0.3</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">0.6</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">1.3</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">2.5</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">DNF</p></td>
<td class="tableblock halign-left valign-top"></td>
<td class="tableblock halign-left valign-top"></td>
<td class="tableblock halign-left valign-top"></td>
</tr>
<tr>
<td class="tableblock halign-left valign-top"><p class="tableblock">VC++ 2013, is_base_of/indirect</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">1.0</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">9.3</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">49.5</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">153.8</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">DNF</p></td>
<td class="tableblock halign-left valign-top"></td>
<td class="tableblock halign-left valign-top"></td>
<td class="tableblock halign-left valign-top"></td>
</tr>
</tbody>
</table>
<table class="tableblock frame-all grid-all stretch">
<colgroup>
<col style="width: 11.1111%;">
<col style="width: 11.1111%;">
<col style="width: 11.1111%;">
<col style="width: 11.1111%;">
<col style="width: 11.1111%;">
<col style="width: 11.1111%;">
<col style="width: 11.1111%;">
<col style="width: 11.1111%;">
<col style="width: 11.1112%;">
</colgroup>
<thead>
<tr>
<th class="tableblock halign-left valign-top"></th>
<th class="tableblock halign-left valign-top">N=100</th>
<th class="tableblock halign-left valign-top">N=200</th>
<th class="tableblock halign-left valign-top">N=300</th>
<th class="tableblock halign-left valign-top">N=400</th>
<th class="tableblock halign-left valign-top">N=500</th>
<th class="tableblock halign-left valign-top">N=600</th>
<th class="tableblock halign-left valign-top">N=700</th>
<th class="tableblock halign-left valign-top">N=800</th>
</tr>
</thead>
<tbody>
<tr>
<td class="tableblock halign-left valign-top"><p class="tableblock">clang++ 3.5.1, recursive</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">0.9</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">4.5</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">13.2</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">30.2</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">DNF</p></td>
<td class="tableblock halign-left valign-top"></td>
<td class="tableblock halign-left valign-top"></td>
<td class="tableblock halign-left valign-top"></td>
</tr>
<tr>
<td class="tableblock halign-left valign-top"><p class="tableblock">clang++ 3.5.1, mp_count/mp_plus</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">0.5</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">1.4</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">3.1</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">6.1</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">DNF</p></td>
<td class="tableblock halign-left valign-top"></td>
<td class="tableblock halign-left valign-top"></td>
<td class="tableblock halign-left valign-top"></td>
</tr>
<tr>
<td class="tableblock halign-left valign-top"><p class="tableblock">clang++ 3.5.1, mp_count/cx_plus</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">0.4</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">1.1</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">2.5</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">5.0</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">DNF</p></td>
<td class="tableblock halign-left valign-top"></td>
<td class="tableblock halign-left valign-top"></td>
<td class="tableblock halign-left valign-top"></td>
</tr>
<tr>
<td class="tableblock halign-left valign-top"><p class="tableblock">clang++ 3.5.1, mp_count/cx_plus2</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">0.4</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">0.9</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">1.8</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">DNF</p></td>
<td class="tableblock halign-left valign-top"></td>
<td class="tableblock halign-left valign-top"></td>
<td class="tableblock halign-left valign-top"></td>
<td class="tableblock halign-left valign-top"></td>
</tr>
<tr>
<td class="tableblock halign-left valign-top"><p class="tableblock">clang++ 3.5.1, is_base_of</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">0.3</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">0.4</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">0.6</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">0.8</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">DNF</p></td>
<td class="tableblock halign-left valign-top"></td>
<td class="tableblock halign-left valign-top"></td>
<td class="tableblock halign-left valign-top"></td>
</tr>
<tr>
<td class="tableblock halign-left valign-top"><p class="tableblock">clang++ 3.5.1, is_base_of/indirect</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">0.4</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">0.9</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">1.6</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">2.5</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">DNF</p></td>
<td class="tableblock halign-left valign-top"></td>
<td class="tableblock halign-left valign-top"></td>
<td class="tableblock halign-left valign-top"></td>
</tr>
</tbody>
</table>
<table class="tableblock frame-all grid-all stretch">
<colgroup>
<col style="width: 11.1111%;">
<col style="width: 11.1111%;">
<col style="width: 11.1111%;">
<col style="width: 11.1111%;">
<col style="width: 11.1111%;">
<col style="width: 11.1111%;">
<col style="width: 11.1111%;">
<col style="width: 11.1111%;">
<col style="width: 11.1112%;">
</colgroup>
<thead>
<tr>
<th class="tableblock halign-left valign-top"></th>
<th class="tableblock halign-left valign-top">N=100</th>
<th class="tableblock halign-left valign-top">N=200</th>
<th class="tableblock halign-left valign-top">N=300</th>
<th class="tableblock halign-left valign-top">N=400</th>
<th class="tableblock halign-left valign-top">N=500</th>
<th class="tableblock halign-left valign-top">N=600</th>
<th class="tableblock halign-left valign-top">N=700</th>
<th class="tableblock halign-left valign-top">N=800</th>
</tr>
</thead>
<tbody>
<tr>
<td class="tableblock halign-left valign-top"><p class="tableblock">g++ 4.9.2, recursive</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">0.7</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">3.6</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">10.4</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">23.2</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">DNF</p></td>
<td class="tableblock halign-left valign-top"></td>
<td class="tableblock halign-left valign-top"></td>
<td class="tableblock halign-left valign-top"></td>
</tr>
<tr>
<td class="tableblock halign-left valign-top"><p class="tableblock">g++ 4.9.2, mp_count/mp_plus</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">0.5</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">1.3</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">2.9</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">5.8</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">9.7</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">15.6</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">22.4</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">32.3</p></td>
</tr>
<tr>
<td class="tableblock halign-left valign-top"><p class="tableblock">g++ 4.9.2, mp_count/cx_plus</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">0.4</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">0.9</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">1.7</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">2.9</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">4.7</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">6.7</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">9.2</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">11.8</p></td>
</tr>
<tr>
<td class="tableblock halign-left valign-top"><p class="tableblock">g++ 4.9.2, mp_count/cx_plus2</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">0.4</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">0.9</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">1.9</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">3.4</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">5.4</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">7.8</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">11.0</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">14.7</p></td>
</tr>
<tr>
<td class="tableblock halign-left valign-top"><p class="tableblock">g++ 4.9.2, is_base_of</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">0.3</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">0.4</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">0.6</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">0.9</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">1.3</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">1.7</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">2.3</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">3.0</p></td>
</tr>
<tr>
<td class="tableblock halign-left valign-top"><p class="tableblock">g++ 4.9.2, is_base_of/indirect</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">0.5</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">1.1</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">2.3</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">4.0</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">6.6</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">9.8</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">13.6</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">18.2</p></td>
</tr>
</tbody>
</table>
</div>
</div>
<div class="sect1">
<h2 id="mp_map_find">mp_map_find</h2>
<div class="sectionbody">
<div class="paragraph">
<p>A map, in the STL sense, is a data structure that associates keys with values
and can efficiently retrieve, given a key, its associated value. For our
purposes, a map will be any list of lists for which the inner lists have at
least one element, the key; the rest of the elements we&#8217;ll consider to be the
associated value. For example, the list</p>
</div>
<div class="listingblock">
<div class="content">
<pre class="highlight"><code>[[A, B], [C, D, E], [F], [G, H]]</code></pre>
</div>
</div>
<div class="paragraph">
<p>is a map with keys <code>A</code>, <code>C</code>, <code>F</code>, and <code>G</code>, with associated values <code>[B]</code>,
<code>[D, E]</code>, <code>[]</code>, and <code>[H]</code>, respectively. We&#8217;ll require unique keys, for reasons
that&#8217;ll become evident later.</p>
</div>
<div class="paragraph">
<p>I&#8217;ll show two other examples of maps, this time using real C&#43;&#43; code:</p>
</div>
<div class="listingblock">
<div class="content">
<pre class="highlight"><code>using Map = mp_list&lt;mp_list&lt;int, int*&gt;, mp_list&lt;void, void*&gt;, mp_list&lt;char, char*&gt;&gt;;</code></pre>
</div>
</div>
<div class="listingblock">
<div class="content">
<pre class="highlight"><code>using Map2 = std::tuple&lt;std::pair&lt;int, int[2]&gt;, std::pair&lt;char, char[2]&gt;&gt;;</code></pre>
</div>
</div>
<div class="paragraph">
<p>The Lisp name of the algorithm that performs retrieval based on key is <code>ASSOC</code>,
but I&#8217;ll call it <code>mp_map_find</code>. <code>mp_map_find&lt;M, K&gt;</code> returns the element of <code>M</code>
whose first element is <code>K</code>. For example, <code>mp_map_find&lt;Map2, int&gt;</code> would return
<code>std::pair&lt;int, int[2]&gt;</code>. If there&#8217;s no such key, it returns <code>void</code>.</p>
</div>
<div class="paragraph">
<p>There&#8217;s almost no need to implement and benchmark the recursive version of
<code>mp_map_find</code>&#8201;&#8212;&#8201;we can be pretty sure it will perform horribly. Still,</p>
</div>
<div class="listingblock">
<div class="content">
<pre class="highlight"><code>template&lt;class M, class K&gt; struct mp_map_find_impl;

template&lt;class M, class K&gt; using mp_map_find = typename mp_map_find_impl&lt;M, K&gt;::type;

template&lt;template&lt;class...&gt; class M, class K&gt; struct mp_map_find_impl&lt;M&lt;&gt;, K&gt;
{
    using type = void;
};

template&lt;template&lt;class...&gt; class M, class T1, class... T, class K&gt;
    struct mp_map_find_impl&lt;M&lt;T1, T...&gt;, K&gt;
{
    using type = mp_if&lt;std::is_same&lt;mp_front&lt;T1&gt;, K&gt;, T1, mp_map_find&lt;M&lt;T...&gt;, K&gt;&gt;;
};</code></pre>
</div>
</div>
<div class="paragraph">
<p>The compile time, in seconds, for <code>N</code> lookups into a map of size <code>N</code>, is as
follows:</p>
</div>
<table class="tableblock frame-all grid-all stretch">
<colgroup>
<col style="width: 11.1111%;">
<col style="width: 11.1111%;">
<col style="width: 11.1111%;">
<col style="width: 11.1111%;">
<col style="width: 11.1111%;">
<col style="width: 11.1111%;">
<col style="width: 11.1111%;">
<col style="width: 11.1111%;">
<col style="width: 11.1112%;">
</colgroup>
<thead>
<tr>
<th class="tableblock halign-left valign-top"></th>
<th class="tableblock halign-left valign-top">N=100</th>
<th class="tableblock halign-left valign-top">N=200</th>
<th class="tableblock halign-left valign-top">N=300</th>
<th class="tableblock halign-left valign-top">N=400</th>
<th class="tableblock halign-left valign-top">N=500</th>
<th class="tableblock halign-left valign-top">N=600</th>
<th class="tableblock halign-left valign-top">N=700</th>
<th class="tableblock halign-left valign-top">N=800</th>
</tr>
</thead>
<tbody>
<tr>
<td class="tableblock halign-left valign-top"><p class="tableblock">VC++ 2013, recursive</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">38.2</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">DNF</p></td>
<td class="tableblock halign-left valign-top"></td>
<td class="tableblock halign-left valign-top"></td>
<td class="tableblock halign-left valign-top"></td>
<td class="tableblock halign-left valign-top"></td>
<td class="tableblock halign-left valign-top"></td>
<td class="tableblock halign-left valign-top"></td>
</tr>
<tr>
<td class="tableblock halign-left valign-top"><p class="tableblock">clang++ 3.5.1, recursive</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">2.5</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">13.7</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">DNF</p></td>
<td class="tableblock halign-left valign-top"></td>
<td class="tableblock halign-left valign-top"></td>
<td class="tableblock halign-left valign-top"></td>
<td class="tableblock halign-left valign-top"></td>
<td class="tableblock halign-left valign-top"></td>
</tr>
<tr>
<td class="tableblock halign-left valign-top"><p class="tableblock">g++ 4.9.2, recursive</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">1.9</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">10.2</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">28.8</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">DNF</p></td>
<td class="tableblock halign-left valign-top"></td>
<td class="tableblock halign-left valign-top"></td>
<td class="tableblock halign-left valign-top"></td>
<td class="tableblock halign-left valign-top"></td>
</tr>
</tbody>
</table>
<div class="paragraph">
<p>I told you there was no point.</p>
</div>
<div class="paragraph">
<p>But, I hear some of you say, you&#8217;re evaluating the else branch even if the
condition is true, and that&#8217;s horribly inefficient!</p>
</div>
<div class="paragraph">
<p>Well, this would only improve the performance by a factor of approximately two
on average, and only if the element is present, but fine, let&#8217;s try it. The
element happens to be present in the benchmark, so let&#8217;s see.</p>
</div>
<div class="listingblock">
<div class="content">
<pre class="highlight"><code>// mp_eval_if

template&lt;bool C, class T, template&lt;class...&gt; class E, class... A&gt;
    struct mp_eval_if_c_impl;

template&lt;class T, template&lt;class...&gt; class E, class... A&gt;
    struct mp_eval_if_c_impl&lt;true, T, E, A...&gt;
{
    using type = T;
};

template&lt;class T, template&lt;class...&gt; class E, class... A&gt;
    struct mp_eval_if_c_impl&lt;false, T, E, A...&gt;
{
    using type = E&lt;A...&gt;;
};

template&lt;bool C, class T, template&lt;class...&gt; class E, class... A&gt;
    using mp_eval_if_c = typename mp_eval_if_c_impl&lt;C, T, E, A...&gt;::type;

template&lt;class C, class T, template&lt;class...&gt; class E, class... A&gt;
    using mp_eval_if = typename mp_eval_if_c_impl&lt;C::value != 0, T, E, A...&gt;::type;

// mp_map_find

template&lt;class M, class K&gt; struct mp_map_find_impl;

template&lt;class M, class K&gt; using mp_map_find = typename mp_map_find_impl&lt;M, K&gt;::type;

template&lt;template&lt;class...&gt; class M, class K&gt; struct mp_map_find_impl&lt;M&lt;&gt;, K&gt;
{
    using type = void;
};

template&lt;template&lt;class...&gt; class M, class T1, class... T, class K&gt;
    struct mp_map_find_impl&lt;M&lt;T1, T...&gt;, K&gt;
{
    using type = mp_eval_if&lt;std::is_same&lt;mp_front&lt;T1&gt;, K&gt;, T1, mp_map_find, M&lt;T...&gt;, K&gt;;
};</code></pre>
</div>
</div>
<div class="paragraph">
<p>There you go:</p>
</div>
<table class="tableblock frame-all grid-all stretch">
<colgroup>
<col style="width: 11.1111%;">
<col style="width: 11.1111%;">
<col style="width: 11.1111%;">
<col style="width: 11.1111%;">
<col style="width: 11.1111%;">
<col style="width: 11.1111%;">
<col style="width: 11.1111%;">
<col style="width: 11.1111%;">
<col style="width: 11.1112%;">
</colgroup>
<thead>
<tr>
<th class="tableblock halign-left valign-top"></th>
<th class="tableblock halign-left valign-top">N=100</th>
<th class="tableblock halign-left valign-top">N=200</th>
<th class="tableblock halign-left valign-top">N=300</th>
<th class="tableblock halign-left valign-top">N=400</th>
<th class="tableblock halign-left valign-top">N=500</th>
<th class="tableblock halign-left valign-top">N=600</th>
<th class="tableblock halign-left valign-top">N=700</th>
<th class="tableblock halign-left valign-top">N=800</th>
</tr>
</thead>
<tbody>
<tr>
<td class="tableblock halign-left valign-top"><p class="tableblock">VC++ 2013, recursive</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">15.6</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">DNF</p></td>
<td class="tableblock halign-left valign-top"></td>
<td class="tableblock halign-left valign-top"></td>
<td class="tableblock halign-left valign-top"></td>
<td class="tableblock halign-left valign-top"></td>
<td class="tableblock halign-left valign-top"></td>
<td class="tableblock halign-left valign-top"></td>
</tr>
<tr>
<td class="tableblock halign-left valign-top"><p class="tableblock">clang++ 3.5.1, recursive</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">1.8</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">9.5</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">DNF</p></td>
<td class="tableblock halign-left valign-top"></td>
<td class="tableblock halign-left valign-top"></td>
<td class="tableblock halign-left valign-top"></td>
<td class="tableblock halign-left valign-top"></td>
<td class="tableblock halign-left valign-top"></td>
</tr>
<tr>
<td class="tableblock halign-left valign-top"><p class="tableblock">g++ 4.9.2, recursive</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">1.4</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">7.0</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">19.7</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">DNF</p></td>
<td class="tableblock halign-left valign-top"></td>
<td class="tableblock halign-left valign-top"></td>
<td class="tableblock halign-left valign-top"></td>
<td class="tableblock halign-left valign-top"></td>
</tr>
</tbody>
</table>
<div class="paragraph">
<p>I told you there was no point.</p>
</div>
<div class="paragraph">
<p>Point or no, to establish that the recursive implementation is inefficient is
not the same as to come up with an efficient one. There are two things that
make the <code>mp_contains</code> techniques inapplicable to our present case: first,
<code>mp_contains</code> only had to return true or false, whereas <code>mp_map_find</code> returns a
type, and second, in <code>mp_contains</code> we knew the exact type of the element for
which we were looking, whereas here, we only know its <code>mp_front</code>.</p>
</div>
<div class="paragraph">
<p>Fortunately, there does exist a language feature that can solve both: C&#43;&#43; can
deduce the template parameters of base classes when passed a derived class. In
this example,</p>
</div>
<div class="listingblock">
<div class="content">
<pre class="highlight"><code>struct K1 {};
struct V1 {};

struct X: std::pair&lt;K1, V1&gt; {};

template&lt;class A, class B&gt; void f(std::pair&lt;A, B&gt; const &amp; p);

int main()
{
    f(X());
}</code></pre>
</div>
</div>
<div class="paragraph">
<p>the call to <code>f(X())</code> deduces <code>A</code> as <code>K1</code> and <code>B</code> as <code>V1</code>. If we have more than
one <code>std::pair</code> base class, we can fix <code>A</code> to be <code>K1</code>:</p>
</div>
<div class="listingblock">
<div class="content">
<pre class="highlight"><code>struct K1 {};
struct V1 {};

struct K2 {};
struct V2 {};

struct X: std::pair&lt;K1, V1&gt;, std::pair&lt;K2, V2&gt; {};

template&lt;class B&gt; void f(std::pair&lt;K1, B&gt; const &amp; p);

int main()
{
    f(X());
}</code></pre>
</div>
</div>
<div class="paragraph">
<p>and <code>B</code> will be deduced as <code>V1</code>.</p>
</div>
<div class="paragraph">
<p>We can retrieve the results of the deduction by returning the type we want:</p>
</div>
<div class="listingblock">
<div class="content">
<pre class="highlight"><code>template&lt;class B&gt; std::pair&lt;K1, B&gt; f(std::pair&lt;K1, B&gt; const &amp; p);</code></pre>
</div>
</div>
<div class="paragraph">
<p>and then using <code>decltype(f(X()))</code> to obtain this return type.</p>
</div>
<div class="paragraph">
<p>What if <code>X</code> doesn&#8217;t have a base of type <code>std::pair&lt;K1, B&gt;</code>? The deduction will
fail and we&#8217;ll get an error that <code>f(X())</code> cannot be called. To avoid it, we can
add an overload of <code>f</code> that takes anything and returns <code>void</code>. But in this
case, what will happen if <code>X</code> has two bases of the form that match the first
<code>f</code> overload, such as for example <code>std::pair&lt;K1, Y&gt;</code> and <code>std::pair&lt;K1, Z&gt;</code>?</p>
</div>
<div class="paragraph">
<p>The deduction will fail, the second overload will again be chosen and we&#8217;ll get
<code>void</code>. This is why we require maps to have unique keys.</p>
</div>
<div class="paragraph">
<p>Here&#8217;s an implementation of <code>mp_map_find</code> based on this technique:</p>
</div>
<div class="listingblock">
<div class="content">
<pre class="highlight"><code>template&lt;class M, class K&gt; struct mp_map_find_impl;

template&lt;class M, class K&gt;
    using mp_map_find = typename mp_map_find_impl&lt;M, K&gt;::type;

template&lt;template&lt;class...&gt; class M, class... T, class K&gt;
    struct mp_map_find_impl&lt;M&lt;T...&gt;, K&gt;
{
    struct U: mp_identity&lt;T&gt;... {};

    template&lt;template&lt;class...&gt; class L, class... U&gt;
        static mp_identity&lt;L&lt;K, U...&gt;&gt;
        f( mp_identity&lt;L&lt;K, U...&gt;&gt;* );

    static mp_identity&lt;void&gt; f( ... );

    using V = decltype( f((U*)0) );

    using type = typename V::type;
};</code></pre>
</div>
</div>
<div class="paragraph">
<p>and its corresponding compile times:</p>
</div>
<table class="tableblock frame-all grid-all stretch">
<colgroup>
<col style="width: 11.1111%;">
<col style="width: 11.1111%;">
<col style="width: 11.1111%;">
<col style="width: 11.1111%;">
<col style="width: 11.1111%;">
<col style="width: 11.1111%;">
<col style="width: 11.1111%;">
<col style="width: 11.1111%;">
<col style="width: 11.1112%;">
</colgroup>
<thead>
<tr>
<th class="tableblock halign-left valign-top"></th>
<th class="tableblock halign-left valign-top">N=100</th>
<th class="tableblock halign-left valign-top">N=200</th>
<th class="tableblock halign-left valign-top">N=300</th>
<th class="tableblock halign-left valign-top">N=400</th>
<th class="tableblock halign-left valign-top">N=500</th>
<th class="tableblock halign-left valign-top">N=600</th>
<th class="tableblock halign-left valign-top">N=700</th>
<th class="tableblock halign-left valign-top">N=800</th>
</tr>
</thead>
<tbody>
<tr>
<td class="tableblock halign-left valign-top"><p class="tableblock">VC++ 2013, deduction</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">0.3</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">0.7</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">1.8</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">3.6</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">6.4</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">10.4</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">16.2</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">DNF</p></td>
</tr>
<tr>
<td class="tableblock halign-left valign-top"><p class="tableblock">clang++ 3.5.1, deduction</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">0.3</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">0.4</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">0.6</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">0.9</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">1.2</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">1.6</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">2.2</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">2.7</p></td>
</tr>
<tr>
<td class="tableblock halign-left valign-top"><p class="tableblock">g++ 4.9.2, deduction</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">0.3</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">0.5</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">0.9</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">1.6</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">2.3</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">3.4</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">4.7</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">6.3</p></td>
</tr>
</tbody>
</table>
<div class="paragraph">
<p>This looks ready to ship.</p>
</div>
<div class="paragraph">
<p>The implementation contains one inefficiency though. If we evaluate
<code>mp_map_find&lt;M, K1&gt;</code>, then <code>mp_map_find&lt;M, K2&gt;</code>, the two nested <code>U</code> types are
the same as they only depend on <code>M</code>, but the compiler doesn&#8217;t know that and
will instantiate each one separately. We should move this type outside
<code>mp_map_find_impl</code> so that it can be reused:</p>
</div>
<div class="listingblock">
<div class="content">
<pre class="highlight"><code>template&lt;class... T&gt; struct <strong>mp_inherit</strong>: T... {};

template&lt;class M, class K&gt; struct mp_map_find_impl;

template&lt;class M, class K&gt;
    using mp_map_find = typename mp_map_find_impl&lt;M, K&gt;::type;

template&lt;template&lt;class...&gt; class M, class... T, class K&gt;
    struct mp_map_find_impl&lt;M&lt;T...&gt;, K&gt;
{
    <strong>using U = mp_inherit&lt;mp_identity&lt;T&gt;...&gt;;</strong>

    template&lt;template&lt;class...&gt; class L, class... U&gt;
        static mp_identity&lt;L&lt;K, U...&gt;&gt;
        f( mp_identity&lt;L&lt;K, U...&gt;&gt;* );

    static mp_identity&lt;void&gt; f( ... );

    using V = decltype( f((U*)0) );

    using type = typename V::type;
};</code></pre>
</div>
</div>
<div class="paragraph">
<p>(This same optimization, by the way, applies to our <code>is_base_of</code> implementation
of <code>mp_contains</code>.)</p>
</div>
<div class="paragraph">
<p>The improvement in compile times on our benchmark is measurable:</p>
</div>
<table class="tableblock frame-all grid-all stretch">
<colgroup>
<col style="width: 11.1111%;">
<col style="width: 11.1111%;">
<col style="width: 11.1111%;">
<col style="width: 11.1111%;">
<col style="width: 11.1111%;">
<col style="width: 11.1111%;">
<col style="width: 11.1111%;">
<col style="width: 11.1111%;">
<col style="width: 11.1112%;">
</colgroup>
<thead>
<tr>
<th class="tableblock halign-left valign-top"></th>
<th class="tableblock halign-left valign-top">N=100</th>
<th class="tableblock halign-left valign-top">N=200</th>
<th class="tableblock halign-left valign-top">N=300</th>
<th class="tableblock halign-left valign-top">N=400</th>
<th class="tableblock halign-left valign-top">N=500</th>
<th class="tableblock halign-left valign-top">N=600</th>
<th class="tableblock halign-left valign-top">N=700</th>
<th class="tableblock halign-left valign-top">N=800</th>
</tr>
</thead>
<tbody>
<tr>
<td class="tableblock halign-left valign-top"><p class="tableblock">VC++ 2013, deduction+mp_inherit</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">0.3</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">0.6</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">1.4</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">2.6</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">4.5</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">7.1</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">10.7</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">DNF</p></td>
</tr>
<tr>
<td class="tableblock halign-left valign-top"><p class="tableblock">clang++ 3.5.1, deduction+mp_inherit</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">0.3</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">0.4</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">0.6</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">0.8</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">1.0</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">1.4</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">1.8</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">2.2</p></td>
</tr>
<tr>
<td class="tableblock halign-left valign-top"><p class="tableblock">g++ 4.9.2, deduction+mp_inherit</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">0.3</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">0.4</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">0.6</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">0.9</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">1.3</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">1.8</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">2.3</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">2.9</p></td>
</tr>
</tbody>
</table>
</div>
</div>
<div class="sect1">
<h2 id="mp_at">mp_at</h2>
<div class="sectionbody">
<div class="paragraph">
<p>With sets and maps covered, it&#8217;s time to tackle vectors. Vectors for us are
just lists, to which we&#8217;ll need to add the ability to efficiently access an
element based on its index. The customary name for this accessor is
<code>mp_at&lt;L, I&gt;</code>, where <code>L</code> is a list and <code>I</code> is an <code>integral_constant</code> that
represents the index. We&#8217;ll also follow the Boost.MPL convention and add
<code>mp_at_c&lt;L, I&gt;</code>, where <code>I</code> is the index of type <code>size_t</code>.</p>
</div>
<div class="paragraph">
<p>The recursive implementation of <code>mp_at</code> is:</p>
</div>
<div class="listingblock">
<div class="content">
<pre class="highlight"><code>template&lt;class L, std::size_t I&gt; struct mp_at_c_impl;

template&lt;class L, std::size_t I&gt; using mp_at_c = typename mp_at_c_impl&lt;L, I&gt;::type;

template&lt;class L, class I&gt; using mp_at = typename mp_at_c_impl&lt;L, I::value&gt;::type;

template&lt;template&lt;class...&gt; class L, class T1, class... T&gt;
    struct mp_at_c_impl&lt;L&lt;T1, T...&gt;, 0&gt;
{
    using type = T1;
};

template&lt;template&lt;class...&gt; class L, class T1, class... T, std::size_t I&gt;
    struct mp_at_c_impl&lt;L&lt;T1, T...&gt;, I&gt;
{
    using type = mp_at_c&lt;L&lt;T...&gt;, I-1&gt;;
};</code></pre>
</div>
</div>
<div class="paragraph">
<p>and the compile times for making <code>N</code> calls to <code>mp_at</code> with a list of size <code>N</code>
as the first argument are:</p>
</div>
<table class="tableblock frame-all grid-all stretch">
<colgroup>
<col style="width: 11.1111%;">
<col style="width: 11.1111%;">
<col style="width: 11.1111%;">
<col style="width: 11.1111%;">
<col style="width: 11.1111%;">
<col style="width: 11.1111%;">
<col style="width: 11.1111%;">
<col style="width: 11.1111%;">
<col style="width: 11.1112%;">
</colgroup>
<thead>
<tr>
<th class="tableblock halign-left valign-top"></th>
<th class="tableblock halign-left valign-top">N=100</th>
<th class="tableblock halign-left valign-top">N=200</th>
<th class="tableblock halign-left valign-top">N=300</th>
<th class="tableblock halign-left valign-top">N=400</th>
<th class="tableblock halign-left valign-top">N=500</th>
<th class="tableblock halign-left valign-top">N=600</th>
<th class="tableblock halign-left valign-top">N=700</th>
<th class="tableblock halign-left valign-top">N=800</th>
</tr>
</thead>
<tbody>
<tr>
<td class="tableblock halign-left valign-top"><p class="tableblock">VC++ 2013, recursive</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">3.6</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">DNF</p></td>
<td class="tableblock halign-left valign-top"></td>
<td class="tableblock halign-left valign-top"></td>
<td class="tableblock halign-left valign-top"></td>
<td class="tableblock halign-left valign-top"></td>
<td class="tableblock halign-left valign-top"></td>
<td class="tableblock halign-left valign-top"></td>
</tr>
<tr>
<td class="tableblock halign-left valign-top"><p class="tableblock">clang++ 3.5.1, recursive</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">1.0</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">5.1</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">15.3</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">DNF</p></td>
<td class="tableblock halign-left valign-top"></td>
<td class="tableblock halign-left valign-top"></td>
<td class="tableblock halign-left valign-top"></td>
<td class="tableblock halign-left valign-top"></td>
</tr>
<tr>
<td class="tableblock halign-left valign-top"><p class="tableblock">g++ 4.9.2, recursive</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">0.9</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">4.7</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">14.2</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">32.4</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">DNF</p></td>
<td class="tableblock halign-left valign-top"></td>
<td class="tableblock halign-left valign-top"></td>
<td class="tableblock halign-left valign-top"></td>
</tr>
</tbody>
</table>
<div class="paragraph">
<p>To improve upon this appalling result, we&#8217;ll again exploit pack expansion into a
function call, but in a novel way. Let&#8217;s suppose that we need to access the
fourth element (<code>I = 3</code>). We&#8217;ll generate the function signature</p>
</div>
<div class="listingblock">
<div class="content">
<pre class="highlight"><code>template&lt;class W&gt; W f( void*, void*, void*, W*, ... );</code></pre>
</div>
</div>
<div class="paragraph">
<p>and then, given a list <code>L&lt;T1, T2, T3, T4, T5, T6, T7&gt;</code>, we&#8217;ll evaluate the
expression</p>
</div>
<div class="listingblock">
<div class="content">
<pre class="highlight"><code>decltype( f( (T1*)0, (T2*)0, (T3*)0, (T4*)0, (T5*)0, (T6*)0, (T7*)0 ) )</code></pre>
</div>
</div>
<div class="paragraph">
<p>The three <code>void*</code> parameters will eat the first three elements, <code>W</code> will be
deduced as the fourth, and the ellipsis will take care of the rest.</p>
</div>
<div class="paragraph">
<p>A working implementation based on this technique is shown below:</p>
</div>
<div class="listingblock">
<div class="content">
<pre class="highlight"><code>// mp_repeat_c

template&lt;std::size_t N, class... T&gt; struct mp_repeat_c_impl
{
    using _l1 = typename mp_repeat_c_impl&lt;N/2, T...&gt;::type;
    using _l2 = typename mp_repeat_c_impl&lt;N%2, T...&gt;::type;

    using type = mp_append&lt;_l1, _l1, _l2&gt;;
};

template&lt;class... T&gt; struct mp_repeat_c_impl&lt;0, T...&gt;
{
    using type = mp_list&lt;&gt;;
};

template&lt;class... T&gt; struct mp_repeat_c_impl&lt;1, T...&gt;
{
    using type = mp_list&lt;T...&gt;;
};

template&lt;std::size_t N, class... T&gt; using mp_repeat_c =
    typename mp_repeat_c_impl&lt;N, T...&gt;::type;

// mp_at

template&lt;class L, class L2&gt; struct mp_at_c_impl;

template&lt;template&lt;class...&gt; class L, class... T,
    template&lt;class...&gt; class L2, class... U&gt;
    struct mp_at_c_impl&lt;L&lt;T...&gt;, L2&lt;U...&gt;&gt;
{
    template&lt;class W&gt; static W f( U*..., W*, ... );

    using R = decltype( f( (mp_identity&lt;T&gt;*)0 ... ) );

    using type = typename R::type;
};

template&lt;class L, std::size_t I&gt; using mp_at_c =
    typename mp_at_c_impl&lt;L, mp_repeat_c&lt;I, void&gt;&gt;::type;

template&lt;class L, class I&gt; using mp_at = mp_at_c&lt;L, I::value&gt;;</code></pre>
</div>
</div>
<div class="paragraph">
<p>and the compile times in the following table show it to be good enough for most
practical purposes.</p>
</div>
<table class="tableblock frame-all grid-all stretch">
<colgroup>
<col style="width: 11.1111%;">
<col style="width: 11.1111%;">
<col style="width: 11.1111%;">
<col style="width: 11.1111%;">
<col style="width: 11.1111%;">
<col style="width: 11.1111%;">
<col style="width: 11.1111%;">
<col style="width: 11.1111%;">
<col style="width: 11.1112%;">
</colgroup>
<thead>
<tr>
<th class="tableblock halign-left valign-top"></th>
<th class="tableblock halign-left valign-top">N=100</th>
<th class="tableblock halign-left valign-top">N=200</th>
<th class="tableblock halign-left valign-top">N=300</th>
<th class="tableblock halign-left valign-top">N=400</th>
<th class="tableblock halign-left valign-top">N=500</th>
<th class="tableblock halign-left valign-top">N=600</th>
<th class="tableblock halign-left valign-top">N=700</th>
<th class="tableblock halign-left valign-top">N=800</th>
</tr>
</thead>
<tbody>
<tr>
<td class="tableblock halign-left valign-top"><p class="tableblock">VC++ 2013, void*</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">0.4</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">1.1</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">2.4</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">4.7</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">DNF</p></td>
<td class="tableblock halign-left valign-top"></td>
<td class="tableblock halign-left valign-top"></td>
<td class="tableblock halign-left valign-top"></td>
</tr>
<tr>
<td class="tableblock halign-left valign-top"><p class="tableblock">clang++ 3.5.1, void*</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">0.4</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">0.7</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">1.2</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">1.9</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">2.7</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">3.8</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">5.0</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">6.6</p></td>
</tr>
<tr>
<td class="tableblock halign-left valign-top"><p class="tableblock">g++ 4.9.2, void*</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">0.3</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">0.5</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">0.9</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">1.3</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">2.1</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">3.0</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">4.2</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">5.5</p></td>
</tr>
</tbody>
</table>
<div class="paragraph">
<p>Are we done with <code>mp_at</code>, then?</p>
</div>
<div class="paragraph">
<p>Let&#8217;s try something else&#8201;&#8212;&#8201;transform the input list <code>[T1, T2, T3]</code> into a map
<code>[[0, T1], [1, T2], [2, T3]]</code>, then use <code>mp_map_find</code> for the lookup:</p>
</div>
<div class="listingblock">
<div class="content">
<pre class="highlight"><code>// mp_map_from_list

template&lt;class L, class S&gt; struct mp_map_from_list_impl;

template&lt;template&lt;class...&gt; class L, class... T, std::size_t... J&gt;
    struct mp_map_from_list_impl&lt;L&lt;T...&gt;, <a href="http://en.cppreference.com/w/cpp/utility/integer_sequence">integer_sequence</a>&lt;std::size_t, J...&gt;&gt;
{
    using type = mp_list&lt;mp_list&lt;mp_size_t&lt;J&gt;, T&gt;...&gt;;
};

template&lt;class L&gt; using mp_map_from_list = typename mp_map_from_list_impl&lt;L,
    <a href="http://en.cppreference.com/w/cpp/utility/integer_sequence">make_index_sequence</a>&lt;mp_size&lt;L&gt;::value&gt;&gt;::type;

// mp_at

template&lt;class L, std::size_t I&gt; struct mp_at_c_impl
{
    using map = mp_map_from_list&lt;L&gt;;
    using type = mp_second&lt;mp_map_find&lt;map, mp_size_t&lt;I&gt;&gt;&gt;;
};

template&lt;class L, std::size_t I&gt; using mp_at_c = typename mp_at_c_impl&lt;L, I&gt;::type;

template&lt;class L, class I&gt; using mp_at = typename mp_at_c_impl&lt;L, I::value&gt;::type;</code></pre>
</div>
</div>
<div class="paragraph">
<p>At first sight, this looks ridiculous, but metaprogramming has its own rules.
Let&#8217;s measure:</p>
</div>
<table class="tableblock frame-all grid-all stretch">
<colgroup>
<col style="width: 11.1111%;">
<col style="width: 11.1111%;">
<col style="width: 11.1111%;">
<col style="width: 11.1111%;">
<col style="width: 11.1111%;">
<col style="width: 11.1111%;">
<col style="width: 11.1111%;">
<col style="width: 11.1111%;">
<col style="width: 11.1112%;">
</colgroup>
<thead>
<tr>
<th class="tableblock halign-left valign-top"></th>
<th class="tableblock halign-left valign-top">N=100</th>
<th class="tableblock halign-left valign-top">N=200</th>
<th class="tableblock halign-left valign-top">N=300</th>
<th class="tableblock halign-left valign-top">N=400</th>
<th class="tableblock halign-left valign-top">N=500</th>
<th class="tableblock halign-left valign-top">N=600</th>
<th class="tableblock halign-left valign-top">N=700</th>
<th class="tableblock halign-left valign-top">N=800</th>
</tr>
</thead>
<tbody>
<tr>
<td class="tableblock halign-left valign-top"><p class="tableblock">VC++ 2013, map</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">0.3</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">0.7</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">1.5</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">2.9</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">5.0</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">7.8</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">11.9</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">DNF</p></td>
</tr>
<tr>
<td class="tableblock halign-left valign-top"><p class="tableblock">clang++ 3.5.1, map</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">0.3</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">0.4</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">0.6</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">0.8</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">1.1</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">1.5</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">1.8</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">2.3</p></td>
</tr>
<tr>
<td class="tableblock halign-left valign-top"><p class="tableblock">g++ 4.9.2, map</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">0.3</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">0.4</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">0.7</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">1.0</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">1.4</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">1.9</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">2.5</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">3.2</p></td>
</tr>
</tbody>
</table>
<div class="paragraph">
<p>Surprise, this is the best implementation.</p>
</div>
</div>
</div>
<div class="sect1">
<h2 id="mp_drop">mp_drop</h2>
<div class="sectionbody">
<div class="paragraph">
<p>It turned out that we didn&#8217;t need the <code>void*</code> trick for <code>mp_at</code>, but I&#8217;ll show
an example where we do: <code>mp_drop</code>. <code>mp_drop&lt;L, N&gt;</code> returns the list <code>L</code> without
its first <code>N</code> elements; or, in other words, it drops the first <code>N</code> elements
(presumably on the cutting room floor) and returns what&#8217;s left.</p>
</div>
<div class="paragraph">
<p>To implement <code>mp_drop</code>, we just need to change</p>
</div>
<div class="listingblock">
<div class="content">
<pre class="highlight"><code>template&lt;class W&gt; W f( void*, void*, void*, W*, ... );</code></pre>
</div>
</div>
<div class="paragraph">
<p>from above to return the rest of the elements, rather than just one:</p>
</div>
<div class="listingblock">
<div class="content">
<pre class="highlight"><code>template&lt;class... W&gt; mp_list&lt;W&gt; f( void*, void*, void*, W*... );</code></pre>
</div>
</div>
<div class="paragraph">
<p>Adding the necessary <code>mp_identity</code> seasoning produces the following working
implementation:</p>
</div>
<div class="listingblock">
<div class="content">
<pre class="highlight"><code>template&lt;class L, class L2&gt; struct mp_drop_c_impl;

template&lt;template&lt;class...&gt; class L, class... T,
    template&lt;class...&gt; class L2, class... U&gt;
    struct mp_drop_c_impl&lt;L&lt;T...&gt;, L2&lt;U...&gt;&gt;
{
    template&lt;class... W&gt; static mp_identity&lt;L&lt;W...&gt;&gt; f( U*..., mp_identity&lt;W&gt;*... );

    using R = decltype( f( (mp_identity&lt;T&gt;*)0 ... ) );

    using type = typename R::type;
};

template&lt;class L, std::size_t N&gt; using mp_drop_c =
    typename mp_drop_c_impl&lt;L, mp_repeat_c&lt;N, void&gt;&gt;::type;

template&lt;class L, class N&gt; using mp_drop = mp_drop_c&lt;L, N::value&gt;;</code></pre>
</div>
</div>
<div class="paragraph">
<p>I&#8217;ll skip the recursive implementation and the performance comparison for this
one. We can pretty much tell who&#8217;s going to win, and by how much.</p>
</div>
</div>
</div>
<div class="sect1">
<h2 id="mp_find_index">mp_find_index</h2>
<div class="sectionbody">
<div class="paragraph">
<p>The final algorithm that I&#8217;ll bring to your attention is <code>mp_find_index</code>.
<code>mp_find_index&lt;L, V&gt;</code> returns an integral constant of type <code>size_t</code> with a
value that is the index of the first occurrence of <code>V</code> in <code>L</code>. If <code>V</code> is not in
<code>L</code>, the return value is the size of <code>L</code>.</p>
</div>
<div class="paragraph">
<p>We&#8217;ll start with the recursive implementation, as usual:</p>
</div>
<div class="listingblock">
<div class="content">
<pre class="highlight"><code>template&lt;class L, class V&gt; struct mp_find_index_impl;

template&lt;class L, class V&gt; using mp_find_index = typename mp_find_index_impl&lt;L, V&gt;::type;

template&lt;template&lt;class...&gt; class L, class V&gt; struct mp_find_index_impl&lt;L&lt;&gt;, V&gt;
{
    using type = mp_size_t&lt;0&gt;;
};

template&lt;template&lt;class...&gt; class L, class... T, class V&gt;
    struct mp_find_index_impl&lt;L&lt;V, T...&gt;, V&gt;
{
    using type = mp_size_t&lt;0&gt;;
};

template&lt;template&lt;class...&gt; class L, class T1, class... T, class V&gt;
    struct mp_find_index_impl&lt;L&lt;T1, T...&gt;, V&gt;
{
    using type = mp_size_t&lt;1 + mp_find_index&lt;L&lt;T...&gt;, V&gt;::value&gt;;
};</code></pre>
</div>
</div>
<div class="paragraph">
<p>and will continue with the compile times for <code>N</code> calls to <code>mp_find_index</code> on a
list with <code>N</code> elements, as usual:</p>
</div>
<table class="tableblock frame-all grid-all stretch">
<colgroup>
<col style="width: 11.1111%;">
<col style="width: 11.1111%;">
<col style="width: 11.1111%;">
<col style="width: 11.1111%;">
<col style="width: 11.1111%;">
<col style="width: 11.1111%;">
<col style="width: 11.1111%;">
<col style="width: 11.1111%;">
<col style="width: 11.1112%;">
</colgroup>
<thead>
<tr>
<th class="tableblock halign-left valign-top"></th>
<th class="tableblock halign-left valign-top">N=100</th>
<th class="tableblock halign-left valign-top">N=200</th>
<th class="tableblock halign-left valign-top">N=300</th>
<th class="tableblock halign-left valign-top">N=400</th>
<th class="tableblock halign-left valign-top">N=500</th>
<th class="tableblock halign-left valign-top">N=600</th>
<th class="tableblock halign-left valign-top">N=700</th>
<th class="tableblock halign-left valign-top">N=800</th>
</tr>
</thead>
<tbody>
<tr>
<td class="tableblock halign-left valign-top"><p class="tableblock">VC++ 2013, recursive</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">3.5</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">DNF</p></td>
<td class="tableblock halign-left valign-top"></td>
<td class="tableblock halign-left valign-top"></td>
<td class="tableblock halign-left valign-top"></td>
<td class="tableblock halign-left valign-top"></td>
<td class="tableblock halign-left valign-top"></td>
<td class="tableblock halign-left valign-top"></td>
</tr>
<tr>
<td class="tableblock halign-left valign-top"><p class="tableblock">clang++ 3.5.1, recursive</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">1.1</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">5.5</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">DNF</p></td>
<td class="tableblock halign-left valign-top"></td>
<td class="tableblock halign-left valign-top"></td>
<td class="tableblock halign-left valign-top"></td>
<td class="tableblock halign-left valign-top"></td>
<td class="tableblock halign-left valign-top"></td>
</tr>
<tr>
<td class="tableblock halign-left valign-top"><p class="tableblock">g++ 4.9.2, recursive</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">0.8</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">4.6</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">13.6</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">DNF</p></td>
<td class="tableblock halign-left valign-top"></td>
<td class="tableblock halign-left valign-top"></td>
<td class="tableblock halign-left valign-top"></td>
<td class="tableblock halign-left valign-top"></td>
</tr>
</tbody>
</table>
<div class="paragraph">
<p>What can we do here?</p>
</div>
<div class="paragraph">
<p>Let&#8217;s go back to <code>mp_contains</code> and look at the "mp_count/cx_plus2"
implementation which we rejected in favor of the inheritance-based one. It
built a <code>constexpr</code> array of booleans and summed them in a <code>constexpr</code>
function. We can do the same here, except instead of summing the array, we can
find the index of the first true value:</p>
</div>
<div class="listingblock">
<div class="content">
<pre class="highlight"><code>template&lt;class L, class V&gt; struct mp_find_index_impl;

template&lt;class L, class V&gt; using mp_find_index = typename mp_find_index_impl&lt;L, V&gt;::type;

template&lt;template&lt;class...&gt; class L, class V&gt; struct mp_find_index_impl&lt;L&lt;&gt;, V&gt;
{
    using type = mp_size_t&lt;0&gt;;
};

constexpr std::size_t cx_find_index( bool const * first, bool const * last )
{
    return first == last || *first? 0: 1 + cx_find_index( first + 1, last );
}

template&lt;template&lt;class...&gt; class L, class... T, class V&gt;
    struct mp_find_index_impl&lt;L&lt;T...&gt;, V&gt;
{
    static constexpr bool _v[] = { std::is_same&lt;T, V&gt;::value... };

    using type = mp_size_t&lt; cx_find_index( _v, _v + sizeof...(T) ) &gt;;
};</code></pre>
</div>
</div>
<div class="paragraph">
<p>The performance of this version is:</p>
</div>
<table class="tableblock frame-all grid-all stretch">
<colgroup>
<col style="width: 11.1111%;">
<col style="width: 11.1111%;">
<col style="width: 11.1111%;">
<col style="width: 11.1111%;">
<col style="width: 11.1111%;">
<col style="width: 11.1111%;">
<col style="width: 11.1111%;">
<col style="width: 11.1111%;">
<col style="width: 11.1112%;">
</colgroup>
<thead>
<tr>
<th class="tableblock halign-left valign-top"></th>
<th class="tableblock halign-left valign-top">N=100</th>
<th class="tableblock halign-left valign-top">N=200</th>
<th class="tableblock halign-left valign-top">N=300</th>
<th class="tableblock halign-left valign-top">N=400</th>
<th class="tableblock halign-left valign-top">N=500</th>
<th class="tableblock halign-left valign-top">N=600</th>
<th class="tableblock halign-left valign-top">N=700</th>
<th class="tableblock halign-left valign-top">N=800</th>
</tr>
</thead>
<tbody>
<tr>
<td class="tableblock halign-left valign-top"><p class="tableblock">clang++ 3.5.1, constexpr</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">0.5</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">1.3</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">2.9</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">DNF</p></td>
<td class="tableblock halign-left valign-top"></td>
<td class="tableblock halign-left valign-top"></td>
<td class="tableblock halign-left valign-top"></td>
<td class="tableblock halign-left valign-top"></td>
</tr>
<tr>
<td class="tableblock halign-left valign-top"><p class="tableblock">g++ 4.9.2, constexpr</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">0.5</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">1.4</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">3.1</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">5.5</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">8.7</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">13.0</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">18.0</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">DNF</p></td>
</tr>
</tbody>
</table>
<div class="paragraph">
<p>which, while not ideal, is significantly better than our recursive punching
bag. But if our compiler of choice is VC++ 2013, we can&#8217;t use <code>constexpr</code>.</p>
</div>
<div class="paragraph">
<p>We may attempt an implementation along the same lines, but with the <code>constexpr</code>
function replaced with ordinary metaprogramming:</p>
</div>
<div class="listingblock">
<div class="content">
<pre class="highlight"><code>template&lt;class L, class V&gt; struct mp_find_index_impl;

template&lt;class L, class V&gt; using mp_find_index = typename mp_find_index_impl&lt;L, V&gt;::type;

template&lt;template&lt;class...&gt; class L, class V&gt; struct mp_find_index_impl&lt;L&lt;&gt;, V&gt;
{
    using type = mp_size_t&lt;0&gt;;
};

template&lt;bool...&gt; struct find_index_impl_;

template&lt;&gt; struct find_index_impl_&lt;&gt;
{
    static const std::size_t value = 0;
};

template&lt;bool B1, bool... R&gt; struct find_index_impl_&lt;B1, R...&gt;
{
    static const std::size_t value = B1? 0: 1 + find_index_impl_&lt;R...&gt;::value;
};

template&lt;bool B1, bool B2, bool B3, bool B4, bool B5,
    bool B6, bool B7, bool B8, bool B9, bool B10, bool... R&gt;
    struct find_index_impl_&lt;B1, B2, B3, B4, B5, B6, B7, B8, B9, B10, R...&gt;
{
    static const std::size_t value = B1? 0: B2? 1: B3? 2: B4? 3: B5? 4:
        B6? 5: B7? 6: B8? 7: B9? 8: B10? 9: 10 + find_index_impl_&lt;R...&gt;::value;
};

template&lt;template&lt;class...&gt; class L, class... T, class V&gt;
    struct mp_find_index_impl&lt;L&lt;T...&gt;, V&gt;
{
    using type = mp_size_t&lt;find_index_impl_&lt;std::is_same&lt;T, V&gt;::value...&gt;::value&gt;;
};</code></pre>
</div>
</div>
<div class="paragraph">
<p>This is still recursive, so we don&#8217;t expect miracles, but it wouldn&#8217;t hurt to
measure:</p>
</div>
<table class="tableblock frame-all grid-all stretch">
<colgroup>
<col style="width: 11.1111%;">
<col style="width: 11.1111%;">
<col style="width: 11.1111%;">
<col style="width: 11.1111%;">
<col style="width: 11.1111%;">
<col style="width: 11.1111%;">
<col style="width: 11.1111%;">
<col style="width: 11.1111%;">
<col style="width: 11.1112%;">
</colgroup>
<thead>
<tr>
<th class="tableblock halign-left valign-top"></th>
<th class="tableblock halign-left valign-top">N=100</th>
<th class="tableblock halign-left valign-top">N=200</th>
<th class="tableblock halign-left valign-top">N=300</th>
<th class="tableblock halign-left valign-top">N=400</th>
<th class="tableblock halign-left valign-top">N=500</th>
<th class="tableblock halign-left valign-top">N=600</th>
<th class="tableblock halign-left valign-top">N=700</th>
<th class="tableblock halign-left valign-top">N=800</th>
</tr>
</thead>
<tbody>
<tr>
<td class="tableblock halign-left valign-top"><p class="tableblock">VC++ 2013, bool&#8230;&#8203;</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">4.7</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">94.5</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">488.3</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">XFA</p></td>
<td class="tableblock halign-left valign-top"></td>
<td class="tableblock halign-left valign-top"></td>
<td class="tableblock halign-left valign-top"></td>
<td class="tableblock halign-left valign-top"></td>
</tr>
<tr>
<td class="tableblock halign-left valign-top"><p class="tableblock">clang++ 3.5.1, bool&#8230;&#8203;</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">0.6</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">2.2</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">5.8</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">12.0</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">21.7</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">35.2</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">DNF</p></td>
<td class="tableblock halign-left valign-top"></td>
</tr>
<tr>
<td class="tableblock halign-left valign-top"><p class="tableblock">g++ 4.9.2, bool&#8230;&#8203;</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">0.6</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">2.4</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">6.5</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">13.2</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">23.8</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">39.1</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">59.0</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">DNF</p></td>
</tr>
</tbody>
</table>
<div class="paragraph">
<p>(where XFA stands for "experimenter fell asleep".)</p>
</div>
<div class="paragraph">
<p>This is an interesting tradeoff for VC++ 2013 and Clang. On the one hand,
this implementation is slower; on the other, it doesn&#8217;t crash the compiler as
easily. Which to prefer is a matter of taste and of stern evaluation of one&#8217;s
needs to manipulate type lists of length 300.</p>
</div>
<div class="paragraph">
<p>Note that once we have <code>mp_drop</code> and <code>mp_find_index</code>, we can derive the
<code>mp_find&lt;L, V&gt;</code> algorithm, which returns the suffix of <code>L</code> starting with the
first occurrence of <code>V</code>, if any, and an empty list otherwise, by using
<code>mp_drop&lt;L, mp_find_index&lt;L, V&gt;&gt;</code>.</p>
</div>
</div>
</div>
<div class="sect1">
<h2 id="conclusion">Conclusion</h2>
<div class="sectionbody">
<div class="paragraph">
<p>In this article, I have shown efficient algorithms that allow us to treat type
lists as sets, maps and vectors, demonstrating various C&#43;&#43;11 implementation
techniques in the process.</p>
</div>
</div>
</div>
</div>
<div id="footer">
<div id="footer-text">
Last updated 2021-08-05 09:42:12 UTC
</div>
</div>
<style>

*:not(pre)>code { background: none; color: #600000; }
/* table tr.even, table tr.alt, table tr:nth-of-type(even) { background: none; } */

</style>
</body>
</html>